Kadane's Algorithm 掃描一次整個數列的所有數值，
在每一個掃描點計算以該點數值為結束點的子數列的最大和（正數和）。
該子數列由兩部分組成：以前一個位置為結束點的最大子數列、該位置的數值。
因為該算法用到了「最佳子結構」
（以每個位置為終點的最大子數列都是基於其前一位置的最大子數列計算得出），
該算法可看成動態規劃的一個例子。
算法可用如下Python代碼實現：
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
該問題的一個變種是：如果數列中含有負數元素，允許返回長度為零的子數列。
該問題可用如下代碼解決：
def max_subarray(A):
max_ending_here = max_so_far = 0
for x in A:
max_ending_here = max(0, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
這種算法稍作修改就可以記錄最大子數列的起始位置。
Kadane算法時間複雜度為O(n)，空間複雜度為O(1)。