https://leetcode.com/problems/maximum-subarray/

| -2 | 1 | -3 | 4 | -1 | 2 | 1 | -5 | 4 |

最初の3つの合計(-2 + 1 -3)はマイナスになるので、 そのため subarray のスタートは 4 もしくは 4以降の数字になる。

合計が正の数になる場合は保持しておく。 変数に0 を代入して、 iterate しながら数字を追加していく。 合計がマイナスになる場合は保持する必要がないので、0 にする。

Time complexity: O(n) Mem complexity: O(1)

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_subarray = nums[0]
        current_subarray = 0
        
        for n in nums:
            if current_subarray < 0:
                current_subarray = 0
            current_subarray += n
            max_subarray = max(max_subarray, current_subarray)
        return max_subarray