Maximum Subarray

Given an array, find the subarray with the maximum sum. Tags: Dynamic Programming

Try It!

Discussion

Video

Solution

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = nums[0]
        cur_total = 0

        for n in nums:
            cur_total += n
            ans = max(ans, cur_total)
            if cur_total < 0:
                cur_total = 0

        return ans