# 53. Maximum Subarray

# Problem

Given an integer array `nums`

, find the

subarraywith the largest sum, and return*its sum*.

**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 <= 10`

^{5}`-10`

^{4}<= nums[i] <= 10^{4}

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

## Bruteforce Solution

**Algorithm**

- Initialize a variable
`maxSubarray = -infinity`

to keep track of the best subarray. We need to use negative infinity, not 0, because it is possible that there are only negative numbers in the array. - Use a
`for`

loop that considers each index of the array as a starting point. - For each starting point, create a variable
`currentSubarray = 0`

. Then, loop through the array from the starting index, adding each element to`currentSubarray`

. Every time we add an element it represents a possible subarray - so continuously update`maxSubarray`

to contain the maximum out of the`currentSubarray`

and itself. - Return
`maxSubarray`

.

```
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_subarray = -math.inf
for i in range(len(nums)):
current_subarray = 0
for j in range(i, len(nums)):
current_subarray += nums[j]
max_subarray = max(max_subarray, current_subarray)
return max_subarray
```

## Dynamic Programming

**Intuition**

Whenever you see a question that asks for the maximum or minimum of something, consider Dynamic Programming as a possibility. The difficult part of this problem is figuring out when a negative number is "worth" keeping in a subarray. This question in particular is a popular problem that can be solved using an algorithm called Kadane's Algorithm. If you're good at problem solving though, it's quite likely you'll be able to come up with the algorithm on your own. This algorithm also has a very greedy-like intuition behind it.

Let's focus on one important part: where the optimal subarray ** begins**. We'll use the following example.

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

We can see that the optimal subarray couldn't possibly involve the first 3 values - the overall sum of those numbers would always *subtract* from the total. Therefore, the subarray either starts at the first `4`

, or somewhere further to the right.

What if we had this example though?

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

We need a general way to figure out when a part of the array is ** worth** keeping.

As expected, any subarray whose sum is *positive* is worth keeping. Let's start with an empty array, and iterate through the input, adding numbers to our array as we go along. Whenever the sum of the array is negative, we know the entire array is not worth keeping, so we'll reset it back to an empty array.

However, we don't actually need to build the subarray, we can just keep an integer variable `current_subarray`

and add the values of each element there. When it becomes negative, we reset it to 0 (an empty array).

**Algorithm**

Initialize 2 integer variables. Set both of them equal to the first value in the array.

`currentSubarray`

will keep the running count of the current subarray we are focusing on.`maxSubarray`

will be our final return value. Continuously update it whenever we find a bigger subarray.

- Iterate through the array, starting with the 2nd element (as we used the first element to initialize our variables). For each number, add it to the
`currentSubarray`

we are building. If`currentSubarray`

becomes negative, we know it isn't worth keeping, so throw it away. Remember to update`maxSubarray`

every time we find a new maximum. - Return
`maxSubarray`

.

**Implementation**

A clever way to update `currentSubarray`

is using `currentSubarray = max(num, currentSubarray + num)`

. If `currentSubarray`

is negative, then `num > currentSubarray + num`

.

```
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
current_subarray = nums[0]
max_subarray = nums[0]
# since current_subarray uses our first element
for i in nums[1:]:
# Work out whether or not we reset our current subarray
# so if we go 1 6, -10
# we do not want to include -10, so we find the max here
# equally if we go -10, -5, 6
# we want to start at 6 instead of -10 as it's higher
current_subarray = max(i, current_subarray + i)
# Our max subarray is the maximum between what we currently have vs the max we've found
# since we do not need to remember which elements make up the max we can just store the value
max_subarray = max(max_subarray, current_subarray)
return max_subarray
```