# Brute force

Try out all O(n^2) subarray and return the max sum.

# Dynamic programming

The basic idea is to record all the maximum subarray that ends at all i. and return the max.

## How to construct a maximum subarray

If we have had a maximum subarray that ends on i – 1, to determine the maximum subarray that ends on i, we can either

- add maximum subarray that ends on i – 1 with nums[i]
- start a new maximum subarray with only nums[i]

We will choose 1 if max_subarray[i – 1] + nums[i] > nums[i].

## Base case:

At the beginning, max_subarray[0] = nums[0]

```
if not nums:
return -1
max_sub = [0] * len(nums)
max_sub[0] = nums[0]
for i in range(1,len(nums)):
max_sub[i] = max(max_sub[i - 1] + nums[i], nums[i])
return max(max_sub)
```

# Divide and conquer

```
def maxSubArray(self, nums: 'List[int]') -> 'int':
"""
"""
def find_mid(nums, l, r, m):
"""
Find the maxsubarray that ends on m,
and the maxsubarray that starts on m + 1, concat th eresult
"""
cur_sum = 0
left_sum = - float('inf')
for i in range(m, l - 1, -1):
cur_sum += nums[i]
left_sum = max(left_sum, cur_sum)
right_sum = - float('inf')
cur_sum = 0
for i in range(m + 1, r + 1):
cur_sum += nums[i]
right_sum = max(right_sum, cur_sum)
return right_sum + left_sum
def find_recur(nums, l, r):
if (l == r):
return nums[l]
m = (l + r) // 2
return max(find_recur(nums, l, m),
find_recur(nums, m + 1, r),
find_mid(nums, l, r, m))
return find_recur(nums, 0, len(nums) - 1)
```

## Bugs

### Didn’t init the left_sum and right_sum to -float(‘inf’).

In case of nums of size 2. The find middle will simply return 0. But the middle didn’t include anything so we should return -inf in that case.

## Find middle

At first, I did something more complicated so my code can strictly divide the three cases:

EG in [1,2,3,4] left would be [1] right would be [4] and middle would be [2,3]. But it leads to complicated code because you have to divide cases into even and odd and so on.

### a simpler solution

We can just use (l + r) //2 as the middle and find the max subarray that contains the middle.

It might overlap.

[10,20,-1,-1] we have l = 0, m = 1 and r = 3. find_recur(nums, l, m) will find the max subarray in [10, 20]. It is 30. find_mid will find the maxsubarray that contains nums[m]. In this case, find_mid finds 30 as well. But overlap is ok because we only want the max.