[Leetcode in mostly plain English] Maximum subarray

Problem statement

Given an integer array nums, find the subarray which has the largest sum and return its sum.

Example 1:

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

Example 2:

Input: nums = [-2, -1]
Output: -1

Example 3:

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

Constraints

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Considerations

• A subarray needs to be a contiguous block of elements.
• Looking at the examples, we can see that this subarray can start and stop at any point inside the given array

Brute force

If you are thinking about nested for loops here, you’re at the right starting point. For each number in the given array, we want to examine the sum of each array containing that element.

Those arrays could contain just the element, or the element and the one next to it, and so on. In example 1, starting at -2 these arrays and their corresponding sums would be as follow:

[-2] = -2 => maxSum = -2
[-2, 1] = -2 + 1 = -1 => maxSum = max(-2, -1) = -1
[-2,1,-3] = -2 + 1 + -3 = -4 => maxSum = max(-1, -4) = -1
...

Once we know the maximum of all arrays starting from one element, we can move on to find the other arrays starting from the next element and repeat the same process.

As you’re moving along, keep track of the max sum in a maxSum variable since that will be our return value. This brute force solution works, but as you can see, the time complexity is O(n²) which is not very good. So how do we improve it?

Dynamic Programming Bottom-up

Let’s take another look at the breakdown of the brute force approach for example 1 and see if we can identify any patterns in the way these sums are calculated.

[-2] = -2 => maxSum = -2
[-2, 1] = -2 + 1 = -1 => maxSum = max(-2, -1) = -1
[-2,1,-3] = -2 + 1 + -3 = -4 => maxSum = max(-1, -4) = -1
...

If you noticed that each subsequent sum is just the previous sum plus the current number that you’re on, then we’re on the right track! At the first number (-2 in our case), since there’s no number before it, let’s say the previous sum is itself -2. Now, let’s rearrange what we had in the block above to include this new prevSum concept to see if we still get the same result as above (we should!).

[-2]
curSum = -2 
=> maxSum = max(prevSum, -2)
=> maxSum = max(-2, -2) = -2

[-2, 1]
curSum = -2 + 1 = prevSum + 1 = -1
=> maxSum = max(prevSum, -1) 
  => maxSum = max(-2, -1) = -1

[-2, 1, -3]
curSum = -2 + 1 + -3 = prevSum + -3 = -4
=> maxSum = max(prevSum, -4)
=> maxSum = max(-1, -4) = -1
...

After you’ve come to terms with what we just did above, it’s just a matter of iterating through the numbers and doing the following steps:

• Calculate the current sum by adding the previous sum to the current number
• If the current sum is less than the previous sum, there’s no point for us to continue adding to the current subarray since we’re looking for a max value here. Set the current sum to be the current number and essentially restart the count from there.
• Compare this current sum to the max sum to see if we need to replace it
• Move the previous sum to the current sum before moving on to the next iteration

By the time you’ve iterated through all of the numbers, maxSum will have the largest sum of a subarray. Cheers!

def maxSubArray(
    nums: List[int],

):
    if len(nums) <= 1:
        return sum(nums)

    maxSum = nums[0]
    prevSum = nums[0]
    for num in nums[1:]:
        curSum = max(num + prevSum, num)
        maxSum = max(curSum, maxSum)
        prevSum = curSum

    return maxSum