Leetcode: Maximum Subarray
Tags: java, python, algorithms, career
Published: 2021-08-17 21:22:53

This is part of a series of Leetcode and other curated solution explanations (index). 
If you liked this solution or found it useful, please like this post.

> [Leetcode Problem #53 (Easy): Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)

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

A subarray is a contiguous part of an array.

 

#### 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 = [1]
Output: 1

#### Example 3:

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

 

####Constraints:
> 1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105

 

**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.

## Solution
This problem can be complex and simple according to how you approach it.

1. Can we find out the pattern to find the max sum possible using a sub-array, say we have a list like 1, 2, 3, 4
the max sum possible would be 10 right ?

2. So can we say that starting from index 0
 - max sum upto index 0 = 1
 - max sum upto index 2 = 3
 - max sum upto index 3 = 6
 - max sum upto index 4 = 10

let's add some fun then!

now the list is 1, -2, 3, 4
 - max sum upto index 0 = 1
 - max sum upto index 2 = `previous MaxSum or current Value  +previous MaxSum? = 1`
 - max sum upto index 3 = 4
 - max sum upto index 4 = 8

so, we can see that even if we summed all the digits, the values comes out to be 8.

let's go for the worse case
-2, 1, -3, 4, -1, 2, 1, -5, 4
- max sum upto index 0 = -2 // by default first digit is max
- max sum upto index 1 = `-2 vs 1+-2` = -1 wait, this doesn't look right, if we have a positive number already, why do we have max sum = -1
ok, lets add another layer of check, 
`max = max(num[i], num[i-1]+num[i], maxSum)`
 - max sum upto index 1 = `-2 vs 1+-2 vs 1` = 1!
- max sum upto index 2 = `1 vs -3 vs -3` = 1
- max sum upto index 3 = `1 vs 4-3 vs 4` = 4
- max sum upto index 4 = `4 vs -1+4 vs -1` = 4
- max sum upto index 5 = `4 vs 2-1 vs 2` = 4 - wait again no! a  series of 4, -1, 2 is ok, we can't just take the last two values, we need a concept of localSum. So
now  
`localMaxSum = nums[i] + Math.max(0, localMaxSum);`
 - max sum upto index 1 = `4 vs -1+2+4 vs 2` = 5!
- max sum upto index 6 = `5 vs 5+1 vs 1` = 6
- max sum upto index 7 = `6 vs 6-5 vs -5` = 6
- max sum upto index 8 = `6 vs 6-5+4 vs 4` = 6

## Implementation
```java
  public static int maxSubArray(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        int maxSum = nums[0];
        int localMaxSum = nums[0];

        for (int i = 1, numsLength = nums.length; i < numsLength; i++) {
            localMaxSum = nums[i] + Math.max(0, localMaxSum);
            maxSum = Math.max(maxSum, localMaxSum);
        }

        return maxSum;
    }
}
```

## Analysis
![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0nh1jukmi57y387ajj6a.png)