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

1. $arr[k]$
2. 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