# O(n) prefix sum solution
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        pre_min = 0
        max_sum = nums[0]
        sum = 0
        for num in nums:
            sum += num
            max_sum = max(max_sum, sum - pre_min)
            pre_min = min(pre_min, sum)
        return max_sum

res = Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4])
print(res) # 6

e53: Maximum Subarray