# Maximum Subarray

This is a LeetCode easy problem. The subarray is contiguous. There is also the maximum sum problem, but that’s easy, just add all positive values. https://www.youtube.com/watch?v=86CQq3pKSUw&ab_channel=CSDojo

Basically, intuitively, you can figure out a $O(n_{3})$ solution, and you can optimize it to $O(n_{2})$.

However, I had trouble understanding how to figure out a $O(n)$ solution. But this is just about breaking down a big problem into a smaller problem. —> Divide and Conquer

Basically, for an $arr$ of length $k$, the maximum will be given by either

- $arr[k]$
- the maximum of the subarray of length $k−1$ + $arr[k]$

You code up an iterative solution.

You can store the old_total

```
max_current, max_global = nums[0], nums[0]
for i in range(1, len(nums)):
max_current = max(nums[i], nums[i] + max_current)
max_global = max(max_current, max_global)
return max_global
```