algorithm - 如何找到在 O(n) 内具有最大和的顺序子数组

Question

给定一个数字数组，包括正数和负数，问题是找到一个顺序子数组，它的和最大，时间复杂度为O(n)，例如，[1,-2,3,10,-4 ,7,2,-5] 是一个数组，子数组 [3, 10, -4, 7, 2] 的和最大的是 18。那么如何在 O(n) 内找到这个子数组呢？谢谢

Answer 1

指向此解决方案的Wiki链接。它称为最大子数组和问题。Kadane 提供了解决方案，它在 O(n) 时间内运行。

Answer 2

这是Python中的解决方案。这个想法是搜索最大连续和。当该总和为负时，您清空列表，如果它不是负数，那么您必须保留这些元素。

l =  [1,-2,3,10,-4,7,2,-5]

def find_max(l):
    s = 0 # Current sum
    lsum = [] # Current subarray
    res = (0, []) # Max value and subarray

    for v in l:
       s += v
       lsum.append(v)
       if s > res[0]:
         res = (s, lsum[:])
       elif s < 0:
         s = 0
         lsum = []

    return res

print find_max(l)

结果：

(18, [3, 10, -4, 7, 2])

Answer 3

这个想法是查看累积系列（将值视为某物的增量/减量），然后找到该系列的低点和随后的高点。

在伪代码中：

sum = 0
low = Integer.MaxValue
highestSumSinceLow = Integer.MinValue
For i = 0 to Array.Length-1
  sum += Array[i]                            // keep track of cumulative value since start
  If sum < low Then                          
    low = sum                                // keep track of lowest sum since start so far
    substart = i + 1                         //    and set substart to next value
  sumsincelow = sum - low                    // calculate sum from that low to here
  If sumsincelow > highestSumSinceLow Then   
    highestSumSinceLow = sumsincelow         // keep track of highest sumsincelow
    subend = i                               //    and set subend to this value
Next i

遍历整个数组后，substart指向subend总和最高的子数组的索引（即highestSumSinceLow）。

这可能是最简单和最有效的解决方案。它是 O(n) 并且不使用临时数组。它从开始到结束只遍历数组一次，并跟踪自开始以来的最低累积总和和自该低点以来的最高总和。