Maximum Subarray

Array Math/Dynamic Programming

Problem

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

For example:

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

Thought Process

• Kadane's Algorithm: The idea is we're going to look at each index and we're going to ask ourselves "What's the maximum subarray ending at this index."

• It's a dynamic programming type problem where we need to identify the optimal substructure, which in this case is the maximum sum ending at that specific index (which will be the local sum). We then have to compare this local sum to the global sum.

Solution

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxLocal = maxGlobal = nums[0]
        for i in range(1, len(nums)):
            maxLocal = max(nums[i], maxLocal+nums[i])
            maxGlobal = max(maxGlobal, maxLocal)
        return maxGlobal
           

Key Facts

• The local maximum subarray is either the subarray at the current index OR the subarray of the current element combined with the previous maximum subarray. We can find the global max subarray from this.

Time Complexity

• Time: $O(n)$
• Space: $O(1)$