python - 用减法折叠数组后找到最大结果

给定一个整数数组，我需要通过重复用它们的差替换任何两个数字来将其减少为一个数字，以产生最大可能的结果。

示例 1 - 如果我有 [0,-1,-1,-1] 数组，则执行 (0-(-1)) 然后 (1-(-1)) 然后 (2-(-1)) 将给出3 作为最大可能输出

Example2- [3,2,1,1] 我们可以得到最大输出 5 { first (1-1) then (0-2) then (3-(-2)}

有人可以告诉我如何解决这个问题吗？

标签： pythonarraysalgorithm

目标是在迭代地减去数组中的两个数字后找到最大结果。

问题主要在算法层面。
很明显，最终结果以绝对值之和为界：

Bound = sum_i abs(a[i])

根据规则x - y，标志可能会经常变化。该算法必须专注于最大化绝对剩余值的总和。

关键是要考虑当我们决定配对两个数字时会发生什么。如果数字的符号不同，结果将有一个最大绝对值，我们可以决定符号。例如，如果这两个值是 (-5, 10)，我们将得到15or -15。将数字与不同的符号相关联，我们只需要选择最终符号，使其与另一个数字的符号不同，例如相邻的数字。

结果是，如果不是所有的符号都相等，我们可以管理结果等于界限。例如：

1 2 -3 4 5 -6 7 -> pair 2 and -3
1 -5 4 5 -6 7   -> pair 1 and -5
-6 4 5 -6 7
-10 5 -6 7
15 -6 7
-21 7
28 = Bound

如果所有符号都相等，则无法达到界限。但是，可以通过选择具有最低绝对值的第一个数字来最小化损失。例如：

 3 4 1 2 2  -> pair 1 and 2
 3 4 -1 2   -> pair -1 and 2
 3 4 -3
 3 -7
 10 = Bound - 2*1

如果所有符号均为负数，则可以使用相同的程序。关键是在第一次“操作”之后，我们得到了一个新的界限，这可以通过“符号规则”来实现。

在这种情况下（所有符号相等），结果等于界限减去最小绝对值的两倍。

当然，必须n = 1单独对待案件：result = a[0];

由此，编写程序相当容易。