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.

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

  1. 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