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.

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

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 ?-
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 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 1 =
- 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[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;
}
}
```

## Top comments (0)