InterviewBit – Max Sum Contiguous Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example:

Given the array [-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray [4,-1,2,1] has the largest sum = 6.

For this problem, return the maximum sum.

---

解題：

1. 用兩個for loop跑出所有子陣列組合之加總數後必定可解，但在網站評分機制設計下應該會timeout；
2. 需想出有什麼方式可以在迴圈內同步更新子陣列的頭尾；
3. 是否可以在一次迴圈（O(N)）內就解決這個問題？
4. 因題目並不需要回傳子陣列，只需回傳加總值，故可將目前最大值儲存，在迴圈中進行比較及更新即可；
5. 以題目舉例試行；如果迴圈當下碰到負數但加總後仍為正數，則應先將其保留，或許後續有可能合併後產生最大值，如示例之index 4 (-1)：

Index	Number	Sum	Current Maximum	Keep
0	-2	-2	-2	-2
1	1	-1	1	1
2	-3	-2	1	1, -3
3	4	2	4	4
4	-1	3	4	4, -1
5	2	5	5	4, -1, 2
6	1	6	6	4, -1, 2, 1
7	-5	1	6	4, -1, 2, 1, -5
8	4	5	6	4, -1, 2, 1, -5, 4

Code:

def maxSubArray(self, A):
    ans = 0
    sumup = 0
    a_len = len(A)
    for i in range(a_len):
        if sumup + A[i] > 0:
            sumup += A[i]
        else:
            sumup = 0
        ans = max(ans, sumup)
    if ans == 0: return max(A)
    else: return ans

將加總是否大於0作為迴圈中是否要將子陣列歸零從新開始之判斷式是相當省力的一步。如果所有的子陣列加總數皆小於0，則只需要找出該陣列中最接近0的負數即可，因負數相加必小於個別負數。

Github: Github – Max Sum Contiguous Subarray