Problem Statement
Explain Kadane’s algorithm for maximum subarray sum and why it works.
Explanation
Kadane keeps a running best ending at the current index. Either extend the previous sum by adding the current number, or start fresh from the current number, whichever is larger. Track the global best seen so far.
It works because any negative running sum only hurts future totals, so dropping it and starting at the current index cannot reduce the best answer. The result comes in linear time with constant space.
Code Solution
SolutionRead Only
def kadane(nums):
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return best