Medium Running Max Arrays & Strings
In plain English: Find the consecutive chunk of numbers in an array that adds up to the largest possible sum.
At each position, decide: extend the current subarray or start fresh. If the running sum goes negative, starting over is always better.
Prompt
Given array a, find the contiguous subarray with the largest sum.
Try to write it from scratch before scrolling down.
Solution
def max_subarray(a):
cur_max = global_max = a[0]
for x in a[1:]:
cur_max = max(x, cur_max + x) # extend or restart
global_max = max(global_max, cur_max)
return global_max
# Test: max_subarray([-2,1,-3,4,-1,2,1,-5,4]) == 6