## DEV Community # Leetcode: Maximum Subarray

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

## 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 = 
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

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

``````  public static int maxSubArray(int[] nums) {

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

int maxSum = nums;
int localMaxSum = nums;

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 