0053. Maximum Subarray

Easy | Array + DP | 40 ms (97.39%), 14.1 MB (71.67%)

❓ Problem Statement

Source: LeetCode - Maximum Subarray GitHub: Solution / Performance

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

✍🏻 Constraints & Example

💡 Ideas

Whenever you see a question that asks for the maximum or minimum of something, consider Dynamic Programming as a possibility.

The difficult part is to figure out whether a negative number is "worth" keeping in a subarray. We could use the concept localMax and globalMax to find out.

• localMax = current sum = previous sum + nums[i] If current sum is smaller than a new number, we take new number as current sum. Otherwise, we keep adding this new number to the current sum.

• globalMax = max sum = final answer We check whether localMax (or current sum) is larger than the globalMax in each iteration. If so, we have new value of max sum

🤖 Python3

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # (base case)
        if len(nums) == 1: return nums[0]
        
        # ==================================================
        #  Array + Dynamic Programming                     =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        curSum = maxSum = nums[0]
        
        for i in range(1, len(nums)):
            curSum = max(nums[i], curSum + nums[i])
            maxSum = max(curSum, maxSum)

        return maxSum

🤖 Java