What is Kadane's algorithm and how does it find the maximum subarray sum in linear time?
It keeps the best sum that ends at each position, and it works out that answer in one pass.
def max_subarray(nums):
best = current = nums[0]
for value in nums[1:]:
current = max(value, current + value)
if current > best:
best = current
return best
So how does it work? The variable current holds the largest sum of a run of numbers that ends at the value you are looking at right now. There are only two ways that run can end. Either the run is just this one value, or the run that ended at the previous value is extended with this one. So you take the bigger of those two, and that is the new value of current.
And the variable best holds the largest of all those values that you have seen, and that is the answer.
So it is O of n for the time, because you go through the list once, and O of 1 for the space, because you only keep two numbers.
The next question in this topic looks at the case that surprises people, and the last one extends the answer.