DEV Community

Cover image for LeetCode Challenge: Maximum Subarray
Bharath Sriraam R R
Bharath Sriraam R R

Posted on

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.
Enter fullscreen mode Exit fullscreen mode

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?

contiguous subarray img

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
Enter fullscreen mode Exit fullscreen mode

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

gintoki surprised gif

Complexity analysis:

Time complexity: O(n^3) 😱
Space complexity: O(1)
Enter fullscreen mode Exit fullscreen mode

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:

subarray sum duplicate sum img

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
Enter fullscreen mode Exit fullscreen mode

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

kagura bored

Complexity analysis:

Time complexity: O(n^2) 😕
Space complexity: O(1)
Enter fullscreen mode Exit fullscreen mode

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...
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Complexity analysis:

Time complexity: O(n) 🤩
Space complexity: O(1)
Enter fullscreen mode Exit fullscreen mode

Now, you be like

gintama some guy

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:

dynamic programming quote

Top comments (0)