## Problem Statement

### Description

Given an integer array `nums`

, find the
subarray with the largest sum, and *return its sum*.

### Examples

#### Example 1:

```
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
```

#### Example 2:

```
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
```

#### Example 3:

```
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
```

### Constraints

`1 <= nums.length <= 105`

`-104 <= nums[i] <= 104`

## Key Insights

In a real interview, it’s a very good idea to discuss the brute force solution first. Starting with the quick and dirty solution demonstrates that you know how to solve problems as opposed to just recite solutions.

Since we’re embracing the messy approach, let’s jump into the weeds and see what we can come up with. We know that we will need to traverse the `nums`

array at least once. While we are at each index `i`

, we need to figure out a way of determining each sub array sum that ends at `i`

.

What if we looped back to beginning from each index `i`

and calculated all of the possible sub array sums. We could keep track of each sum and store the result in a final answer `ans`

variable. This would give us an `O(N`

solution that we could optimize. See the following code.^{2})

```
def maxSubArray(nums: List[int]) -> int:
n = len(nums)
ans = nums[0]
sub = 0
for i in range(n):
for j in range(i, -1, -1):
sub += nums[j]
ans = max(ans, sub)
sub = 0
return ans
```

This brute force approach is a good start, but it won’t get you the job. We’re going to need to do better! As we evaluate this problem, we notice that we are redoing a lot of work each time we calculate the the sub array sums. We also recognize that the solution to the overall problem can be solved by using the results of smaller subproblems. This looks like a **Dynamic Programming** problem!

Let’s start with the smallest possible subproblem and see what we can come up with. In the following example, the sum of the sub array ending at index `i = 0`

is `-2`

.

```
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
```

At `i = 1`

, the possible sub arrays are `[1]`

and `[-2, 1]`

with sub array sums of `1`

and `-1`

respectively. At `i=0`

, the largest sub array sum is `ans = -2`

; and at `i = 1`

, the largest sub array sum is `ans = 1`

. If we know the sub array sum at `i = 0`

, we can find the sub array sum at `i = 1`

.

Since we are looking for the largest sub array sum in the array, we can actually make a choice at each index `i`

. If the adding `nums[i]`

to the running sub array sum results in a value that is larger than `nums[i]`

, we can continue to build out the current sub array. However, if `nums[i]`

is greater than the sub array that can be created by adding `nums[i]`

to the current running total, we start a new sub array at index `i`

, whose new sub array sum is `nums[i]`

. In so doing, we can actually solve the problem in one pass.

If we maintain a `dp`

array, we can store the sum of the largest sub array sum that ends at index `i`

. As we traverse through the `nums`

array, we can maintain an `ans`

variable to store the value of the largest overall sub array sum.

## Python Solution

```
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
ans = nums[0]
"""
-2, 1, -3, 4, -1, 2, 1, -5, 4
^
"""
for i in range(1, n):
dp[i] = max(dp[i-1] + nums[i], nums[i])
ans = max(ans, dp[i])
return ans
```

### Manual Execution

i | nums | dp | ans |
---|---|---|---|

`0` | `-2` | `-2` | `-2` |

`1` | `1` | `1` | `1` |

`2` | `-3` | `-2` | `1` |

`3` | `4` | `4` | `4` |

`4` | `-1` | `3` | `4` |

`5` | `2` | `5` | `5` |

`6` | `1` | `6` | `6` |

`7` | `-5` | `1` | `6` |

`8` | `4` | `5` | `6` |