Maximum Subarray

Intuition

The maximum sum of a sequence with the end index j is the sum of A[0:j + 1] minus the minimum sum of A[0:i] for any i <= j.

Solution


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        s = 0
        min_s = 0
        max_s = nums[0]
        for num in nums:
            s += num
            max_s = max(max_s, s - min_s)
            min_s = min(min_s, s)
        return max_s