Kadane’s Algorithm

For Maximum Contiguous Subarray problem.

Largest Sum Contiguous Subarray

# Initialize our variables using the first element.
cur_sum = max_sum = nums[0]
 
# Start with the 2nd element since we already used the first one.
for num in nums[1:]:
    # If current_sum is negative, throw it away. Otherwise, keep adding to it.
    cur_sum = max(num, cur_sum + num)
    max_sum = max(max_sum, cur_sum)
 
return max_sum

Intuition
- As long as the subarray sum is positive, it’s still worth keeping.
- When it becomes negative, we should throw it away.
- But remember to update the max sum obtained so far.

What we’ve learned:

Don’t give up easily if you find that num[i] is negative. There might be much more positive digits ahead!
However, when you look back, and you find that the current_sum is already negative, please do give it up ruthlessly.
But before you throw it away, remember to update best_sum, as at the end of the day, this is the best thing you’ve obtained so far.