題目

53. Maximum Subarray 給定一個整數陣列nums，找到子陣列其總和最大並返回其總和。

使用preSum

preSum(i)代表陣列nums[0:i](包含i)的總合，子陣列nums[i:j]的總和: preSum(j)-preSum(i-1) 當前指標位置cr，到cr前最小的preSum min_sum = min(preSum(0),...,preSum(cr-1))，那麼假設最大總和的子陣列的最後一個元素為cr，該子陣列的總合為preSum(cr)-min_sum。

以下圖為例子，指標cr = 0，到cr前最小的preSum: minSum = 0，結尾為cr的最大總和的子陣列ans_0 = preSum(0)-minSum = -2 - 0 = -2。

cr依序遍歷nums的每個元素…

指標cr = 4，到cr前最小的preSum: minSum = -2+1+(-3) = -4，結尾為cr的最大總和的子陣列ans_4 = preSum(cr)-minSum = -1-(-4) = 3。

指標cr = 5，minSum = -2+1+(-3) = -4，結尾為cr的最大總和的子陣列ans_5 = preSum(cr)-minSum = 1-(-4) = 5。

cr每前進一步，就會計算出一個結尾為cr的最大子陣列總和ans_cr，回傳最大的ans_cr就是最大子陣列總和。

時間複雜度

由於每次指標cr向前走一步，都需要更新一次preSum, min_sum, 和最大的ans，因此時間複雜度為$O(N)$。

實作

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sum = 0
        min_sum = 0
        ans = -inf
        for num in nums:
            sum += num
            ans = max(ans, sum-min_sum)
            min_sum = min(sum, min_sum)
        return ans

動態規劃

先思考一下，如果子陣列的結尾位置為i，那麼最大總和的子陣列總和可以怎麼計算呢?

以cr[i]代表nums[i]為結尾的總和最大nums子陣列，在已知cr[i-1]的前提下，cr[i]有兩種可能:

加上以前一個位置結尾的子陣列最大總和: cr[i-1]+nums[i]
```
 nums = [-2,1,-3,4,-1,2,1,-5,4]
                        ^
                        i
```
當我們要計算結尾為index i = 6的子陣列最大總和, 以cr[i-1]為結尾的最大子陣列總和為cr[5]=1，nums[i]=1加上以前一個位置結尾的子陣列最大總和大於從當前i這個位置算起，因此cr[i] = cr[i-1]+nums[i] = cr[5]+nums[6] = 2
不包含前一個位置的最大總和: nums[i]
```
 nums = [-2,1,-3,4,-1,2,1,-5,4]
            ^
            i
```
當我們要計算結尾為index i =1的子陣列最大總和, 以cr[i-1]為結尾的最大子陣列總和為cr[0]=-2，加上以前一個位置結尾的子陣列最大總和不如從當前i這個位置算起，因此cr[i] = nums[i]

回到這個題目，我們可以使用迴圈，去計算每個結尾位置為i，最大總和的子陣列總和，只保留最大的總和，就是整個陣列的最大子陣列總和啦~

時間複雜度

每次藉由前一個cr[i-1]來計算以當前index為結尾的子陣列最大總和cr[i]，時間複雜度是$O(1)$，針對每個nums[i]為結尾都需要一次計算，因此時間複雜度為$O(N)$。

實作

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cr = 0
        ans = -inf
        for num in nums:
            cr = max(cr+num, num)
            ans = max(ans, cr)
        return ans