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

Constraints:

• 1 <= nums.length <= 3 * 10^4

• -10^5 <= nums[i] <= 10^5

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Input: nums = [1]
Output: 1

Input: nums = [5,4,-1,7,8]
Output: 23

💡 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

class Solution {
    /**
     * @time  : O(n)
     * @space : O(1)
     */

    public int maxSubArray(int[] nums) {
        /* base case */
        if(nums.length == 1) return nums[0];
    
        int curSum = nums[0], maxSum = nums[0];
        
        for(int i=1 ; i<nums.length ; i++){
            curSum = Math.max(nums[i], curSum + nums[i]);
            maxSum = Math.max(curSum, maxSum);
        }
        
        return maxSum;
    }
}