math - 如何获得具有以下条件的数组的最大和？

Question

假设提出的问题如下：

在火星上生活着一群蠕虫。每个蠕虫都表示为一维数组中的元素。蠕虫决定互相吃掉，但任何蠕虫都只能吃它最近的邻居。每个蠕虫都有一个预设的能量（即元素的值）。在火星上，法律规定当一条能量为x的蠕虫i吃掉另一条能量为y的蠕虫时，第i个蠕虫的最终能量变为xy。允许蠕虫具有负能量水平。

找到最后一个站立的蠕虫的能量最大值。

Sample data:
0,-1,-1,-1,-1 has answer 4.
2,1,2,1 has answer 4.

解决这个问题的合适逻辑是什么？

标签： mathlogicdynamic-programming

Answer 1

这个问题有一个非常简单的O(N)解决方案。

如果数组中的任何两个成员具有不同的符号，则答案是所有元素的绝对值之和。

要了解原因，请想象数组中有一个正值，所有其他元素都是负数（示例 1）。现在最好的策略是保持这个值是积极的，并逐渐吃掉所有的邻居来增加这个积极的价值。正值的位置无关紧要。在单个负面元素的情况下，该策略是相同的。

在更一般的情况下，如果一个大小数组N有不同符号的值，我们总是可以找到一个大小N-1不同但符号不同的数组，因为必须有一对不同符号的邻居，我们可以将它们组合成多个任意我们喜欢的标志。

例如这个数组：[1,2,-5,4,-10]

1. 我们可以组合 (2,-5) 或 (4,-10)。让我们结合 (4,-10) 得到[1,2,-5,-14]
2. 我们现在只能取 (2,-5)。所以我们现在的数组是：[1,-7,-14]
3. 同样只有 (1,-7) 可能。但这一次我们必须保持综合价值为正。所以我们剩下：[8,-14]
4. 最终组合给我们22, 所有绝对值的总和。

如果所有值都具有相同的符号，我们的第一步是生成一个相反的符号，将相邻对组合在一起，并尽可能少地“成本”。直观地说，我们不想在这个转换上浪费两个大数字。如果我们取x,y邻居对，当组合时（相反符号的）新值将是abs(x-y)。由于结果只是绝对值的总和，我们可以将其解释为 - “失去” abs(x)，abs(y)从最大可能的输出和“获得”abs(x-y)来代替。所以使用这对符号转换的“成本”是abs(x)+abs(y)-abs(x-y)。由于我们需要最小化这个成本，我们从具有最低这个值的初始数组邻居对中选择。

因此，如果我们采用上述数组，但现在所有值都是正数[1,2,5,4,10]：

1. (1,2)转换为 -1 的“成本”是1+2-abs(-1)=2.
2. (2,5)转换为 -3 的“成本”是2+5-abs(-3)=4.
3. (5,4)转换为 -1 的“成本”是5+4-abs(-1)=8.
4. (4,10)转换为 -6 的“成本”为4+10-abs(-6)=8.

因此，我们将pair转换(1,2)为-1。然后只需将结果数组的绝对值相加即可得到 20。请注意，该值恰好比我们之前的示例小 2。