給定A = [a0, a1, ..., an-1],如何使得slice的和 sum(A[p], A[p+1], ..., A[q]) 有最大值(slice長度可以為0)?有個有名的Kadane’s Algorithm可以解決這個問題。

Kadane’s Algorithm

如果已知A[:i]的max sum,那麼A[:i+1]的max sum必定包含或不包含A[:i]的prefix。

對每個A內的元素,求那個位置所能達到的sum最大值,令其為max_ending_here

包含prefix的情況下,max_ending_here為prefix加上當前元素a;不包含prefix的情況下,max_ending_here為0。(不包含的情況,表示max_ending_here + a小於0,就直接捨棄掉prefix和當前元素a,令max_ending_here歸零,從下一個元素開始計算)

def max_slice(A):
    max_ending_here = max_so_far = 0
    for a in A:
        max_ending_here = max(0, max_ending_here + a)
        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

參考

Maximum Subarray Problem - Wikipedia

覺得這篇文章對你有幫助的話,歡迎分享👉