# 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
