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 solution, and you can optimize it to .
However, I had trouble understanding how to figure out a solution. But this is just about breaking down a big problem into a smaller problem. —> Divide and Conquer
Basically, for an of length , the maximum will be given by either
- the maximum of the subarray of length +
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