Leetcode題解 Python： 四月挑戰DAY3 Maximum Subarray

給一串數列，要找出當中各連續部分(contiguous subarray)的最大總和為何。

數字的範圍是甚麼？整數，包含正負整數。

按照題目規則，先用暴力破解法的思維：找出所有連續子串的總和，再從中找出最大值即可。
這樣時間複雜度會是 O(n(n-1)/2) → O(n**2)。

至少能夠先有一個可行的方法，接著繼續思考有沒有比 O(n**2) 更少次的方法？

Follow up:
「If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.」

存在著 O(n) 的方法，不過題目希望能夠拆散數列再各個處理的方式(分治法)。


先提 O(n) 的方法。

既然是 O(n)，架構通常是一個「 for in 」，先寫上去再思考就好。需要回傳最大總和，所以可以命名一個 largestSum，最後 return largestSum。

如果要跑完一回就能找到答案，得在過程中記錄甚麼，或是判斷甚麼。

觀察一下數列，思考：遇到正的就累加起來，如果數列都是正整數，加完就是最大總和。那遇到負的部分呢？

這裡想到了累加，所以命名一個 accu 的變數，存放當前累加的結果。

如果遇到負整數，會使得當前累加會減少，所以先把當前的累加值保存下來，然後再把數字加上去。

將下來再做一些細部條件判斷，就能完成 O(n) 的解法。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:       
        largestSum = nums.pop(0) 
        nowAccu = largestSum 
        for num in nums:
            if num < 0:
                if nowAccu < 0: 
                    largestSum = max(largestSum, num)
                else:
                    largestSum = max(largestSum, nowAccu)
                    nowAccu += num
            else:
                if nowAccu < 0: nowAccu = num
                else: nowAccu += num                
        largestSum = max(largestSum, nowAccu) #最後一項
        return largestSum

至於分治法要怎麼寫？覺得麻煩就跳過。目前的概念是分成正負組合，再處理成各區域最大總和，從中回傳最大值。
。