algorithm - 如何找到一系列整数中可能的最低值？

Question

我有一个像这样的整数序列(正数和负数):

12,-54,32,1,-2,-4,-8,12,56,-22,-21,4,17,35

而且我需要找到可能采用此序列的任何子序列(当然还有该子序列的起始索引和结束索引)的最坏结果(较小的值总和)。

有没有一种方法不是 2^n(一个一个地计算所有可能的序列)？

例如，使用这个简单的序列:

1,2,-3,4,-6,4,-10,3,-2

值的较小总和将是子序列:

-6,4,-10 (with start index 4 and end index 6)

Answer 1

通过改变每一项的符号，寻找最小值的问题可以转化为寻找最大值的问题。

对于最大子序列，存在众所周知的算法，参见例如here .

您可以转换您的列表并应用所述算法或稍微修改算法本身(最小值而不是最大值或负值而不是加号)以便使用您的原始列表。