# 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