LeetCode Challenge: Maximum Subarray
Tags: computerscience, beginners, leetcode, problemsolving
Published: 2020-04-10 14:57:41


# 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?
![contiguous subarray img](https://dev-to-uploads.s3.amazonaws.com/i/pbydmiv5qg81ef8ggwej.png)

# 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:__
```python
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.

![gintoki surprised gif](https://dev-to-uploads.s3.amazonaws.com/i/13vtdz5iw1rtaulosyjc.gif)

__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:

![subarray sum duplicate sum img](https://dev-to-uploads.s3.amazonaws.com/i/oahp26l9ed6bcpyfx49r.png)

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:__
```python
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).

![kagura bored](https://dev-to-uploads.s3.amazonaws.com/i/7vg94eoxn3l0pg5modvl.gif)

__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:__
```python
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

![gintama some guy](https://dev-to-uploads.s3.amazonaws.com/i/r0yn7ou4eor9hekpoeud.gif)

# 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](https://en.wikipedia.org/wiki/Dynamic_programming) 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](https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/tutorial/) 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
{% replit @13point5/Maximum-Subarray %}


There's a saying related to dynamic programming:

![dynamic programming quote](https://dev-to-uploads.s3.amazonaws.com/i/r61as7fq5d389qy7j5yx.png)