Maximum subarray problem是在一维数组中找到一个连续的子数组，使该子数组的和为最大。
例如，对一个数组 −2, 1, −3, 4, −1, 2, 1, −5, 4，其连续子数组中和最大的是 4, −1, 2, 1, 其和为6。

Kadane’s algorithm

Kadane’s algorithm 从一个简单的归纳问题开始：如果我们知道在位置 i 的最大子数组和，那么在位置 i+1 的最大子数组和会是什么？有两种情况：

  • 数组的最大子数组和在位置 i+1 ，包括了在位置 i 的最大子数组和
  • 在位置 i+1 不是数组的最大子数组和

因此，我们可以通过遍历数组，来计算每个位置的最大子数组和，我们只需要跟踪其中最大的那个。
python 代码如下：

1
2
3
4
5
6
7
8
def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far
    #max_ending_here 现在位置的最大子数组和
    #max_so_far 目前为止所以位置的最大的子数组和

修改：跟踪最大子数组和的起始位置和结束位置

跟踪结束位置
结束位置是比较简单的，只需要注意 max_so_far 改变的时候

1
2
3
4
5
6
7
8
9
10
11
12
def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    i, end = 0, 0
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        if max_so_far < max_ending_here:
            end = i + 1
            max_so_far = max_ending_here
        i += 1
    return max_so_far, end
    #max_ending_here 现在位置的最大子数组和
    #max_so_far 目前为止所以位置的最大的子数组和

跟踪起始位置
起始位置则需注意 max_ending_here 改变时。当 max_ending_here 变为 x 的时候，说明当前位置元素大于之前所有位置的最大子数组和，所以从这里重新开始计算最大子数组和，即为起始位置

1
2
3
4
5
6
7
8
9
10
11
12
def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    i, start = 0, 0
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        if max_ending_here == x:
            start = i + 1
        max_so_far = max(max_so_far, max_ending_here)
        i += 1
    return max_so_far, start
    #max_ending_here 现在位置的最大子数组和
    #max_so_far 目前为止所以位置的最大的子数组和