# LeetCode 53. Maximum Subarry

## The Problem

Link to original problem on Leetcode.

Given an integer array `nums`

, find the contiguous subarray (containing at least one number) which has the largest sum and return *its sum*.

## Examples

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 = [0]
Output: 0
```

Example 4:

```
Input: nums = [-1]
Output: -1
```

Example 5:

```
Input: nums = [-100000]
Output: -100000
```

## Constraints

- 1 <=
`nums.length`

<= 3 * 10^{4} - -10
^{5}<=`nums[i]`

<= 10^{5}

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.

## My Solution

### Naïve Approach

The worst thing I can think of would be to compute the sum of every conceivable subarray. This would be $O(n{^3})$ time complexity and $O(1)$ space complexity.

```
// Bad, don't do this
const maxSubArray = nums => {
let sum = nums[0];
for (let i = 0; i < nums.length; i++) {
for (let j = i; j < nums.length; j++) {
// I'm using slice and reduce to get the subarray
// sum instead of writing a third for loop,
// because why not?
const newSum = nums.slice(i, j + 1).reduce((acc, curr) => {
return acc + curr;
}, 0);
sum = Math.max(sum, newSum);
}
}
return sum;
};
```

This code passed Leetcode’s example test cases, but times out when submitted. No surprises there!

It can be improved to $O(n{^2})$ time by noticing that we don’t need to compute each piece of each subarry. For example, with an array `[2, 5, -3, 4]`

, I would start with `2`

, `2+5`

, then `2+5-3`

, then `2+5-3+4`

for the first loop of `i`

. See how I recompute every value every time? Instead, I could do it as `2`

, `2+5`

, `7-3`

, `4+4`

. Here’s what that would look like:

```
// Better but still bad, don't do this either
const maxSubArray = nums => {
let sum = nums[0];
for (let i = 0; i < nums.length; i++) {
let leftSideSum = 0;
for (let j = i; j < nums.length; j++) {
leftSideSum += nums[j];
sum = Math.max(sum, leftSideSum);
}
}
return sum;
};
```

### Kadane’s Algorithm

I did some research and found Kadane’s algorithm for solving this problem in $O(n)$ time. It breaks the problem down into the question: would I get a higher sum by continuing the largest subarry ending at index `i - 1`

, or just starting a new subarry at `i`

? To do this, it keeps track of the best sum we’ve seen so far and the best subarray sum ending at `i`

. No lie, this took some time to wrap my head around. Here’s an implementation.

```
// Much improved, could do this
const maxSubArray = nums => {
let current = -Infinity,
best = -Infinity;
for (let i = 0; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
best = Math.max(best, current);
}
return best;
};
```