LeetCode Challenge: Maximum Subarray

Problem

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

Example:

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

Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

What is a contiguous subarray?

Approach 1: A very intuitive and insanely slow solution

Now, that you know what a contiguous subarray is, the only thing left to do is to figure out which subarray has the maximum sum.

Since we don't know the length or position of the subarray we seek, we can perform an exhaustive search of all possible subarray lengths starting from all possible indices.

Algorithm:

1. Initialize the answer to the first element of the array
2. Iterate sub_len from 1 to length of the array
3. Iterate start_idx from 0 to length of the array
4. Assign answer to the maximum among the previous answer and sum of elements in the array from index start_idx to start_idx + sub_len

Code:

def approach1(nums):
    ans = nums[0]
    for sub_len in range(1, len(nums) + 1):
        for start_idx in range(len(nums)):
            ans = max(ans, sum(nums[start_idx : start_idx + sub_len]))
    return ans

Pretty sweet code right? Have a look at the Time complexity.

Complexity analysis:

Time complexity: O(n^3) 😱
Space complexity: O(1)

Approach 2: Slightly improved version of Approach 1

If you analyze the weakness of the previous algorithm, for each valid start_idx we calculate the sum by iterating from start_idx to start_idx + sub_len which is duplicate work.

Why is it duplicate work?
In each subarray, we leave 1 element from the start and add 1 element to the end. Which means the sum of the remaining elements from the previous subarray need not be calculated. Here's an illustration to simplify it:

Which means, we can subtract the first element of the previous subarray and add the last element of the new subarray to the sum of the previous subarray.

Algorithm:

1. Initialize the answer to the first element of the array
2. Iterate sub_len from 1 to length of the array
3. Iterate start_idx from 0 to length of the array
4. Assign answer to the maximum among the previous answer and sum of elements in the array from index start_idx to start_idx + sub_len

Code:

def approach2(nums):
    ans = nums[0]
    length = len(nums)

    for sub_len in range(1, length + 1):
        subsum = sum(nums[0 : sub_len])
        ans = max(ans, subsum)

        for start_idx in range(1, length):
            if (start_idx + sub_len - 1) < length:
                subsum = subsum - nums[start_idx - 1] + nums[start_idx + sub_len - 1]
                ans = max(ans, subsum)
            else:
                break

    return ans

This is better but you'll still get a TLE(at least in Python you will).

Complexity analysis:

Time complexity: O(n^2) 😕
Space complexity: O(1)

Approach 3:

Clearly, this kind of thinking is not getting us anywhere so time to take a step back and think differently.

Let's say we have a subarray with sum X and the next element is Y.
If X+Y < Y then we would be better off starting a new subarray from Y because it makes no sense to have a subarray with a sum less than its greatest element.

Here's an example:

Array: [-2,1,-3,4,-1,2,1,-5,4]

sum = -2 because it's the initial element

sum + 1 = -1 and -1 < 1 so we wouldn't consider the subarray [-2, 1]

So, sum = 1

sum + (-3) = -2 and -2 > -3 so we consider the subarray [1, -3]

sum + 4 = 2 and 2 < 4 so we don't consider [1, -3, 4] instead we start a new subarray from 4.

So, sum = 4 and subarray = [4]

and so on...

This looks good but how do we get the maximum subarray sum?
Simple, we use another variable to keep track of the maximum subarray sum whenever we change the subarray.

Algorithm:

1. Initialize ans and subarr_sum to the first element of the array
2. Iterate from index 1 to last index of the array
3. Assign subarr_sum = max(nums[i], nums[i] + subarr_sum)
4. Assign ans = max(ans, subarr_sum)
5. return ans

Code:

def approach3(nums):
    ans = nums[0]
    subarr_sum = nums[0]

    for i in range(1, len(nums)):
        subarr_sum = max(nums[i], nums[i] + subarr_sum)
        ans = max(ans, subarr_sum)

    return ans

Complexity analysis:

Time complexity: O(n) 🤩
Space complexity: O(1)

Now, you be like

Summary

Wasn't the solution behind Approach 3 pretty intuitive?
Guess what! The algorithm used in it is an example of Dynamic Programming!

What is Dynamic Programming?

Here's what Wikipedia says:

Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

You can read about it in detail over here but basically, you identify sub-problems and somehow find solutions to them and save it so that you don't calculate it again.

Where was this used here?
The variable subarr_sum was used to store the maximum subarray sum so far, which means at any index we knew the answer to the problem so far which is the subproblem. All we had to do was make a decision whether to include this element in the subarray or to start a new subarray.

Here's the replit

There's a saying related to dynamic programming: