Kadane's Algorithm: Maximum Subarray in One Pass
Maximum Subarray (LeetCode 53) asks for the largest sum of any contiguous subarray. Brute force checks every pair of endpoints, which is O(n²). Kadane's algorithm does it in O(n) with O(1) memory.
The insight
At each index, the best subarray ending here either extends the previous best one or starts fresh. You start fresh whenever the running sum has gone negative, because a negative prefix can only make things worse.
def max_subarray(nums):
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return best
Initialising with nums[0] (not 0) correctly handles arrays that are all negative, a case interviewers like to test.
Variations
- Return the indices: remember where
curwas last reset; updatestart/endwheneverbestimproves. - Maximum Product Subarray (152): track both the max and the min product, because a negative number flips them.
- Circular array (918): answer = max(normal Kadane, total sum minus the minimum subarray), unless every number is negative.
- Best Time to Buy and Sell Stock (121): Kadane on the daily price differences.
Explaining it as DP
Say: "dp[i] is the best sum of a subarray ending at i; dp[i] = max(nums[i], dp[i-1] + nums[i]), and I only need the previous value, so I keep one variable." Framing it this way shows you understand why it works, not just the trick.
Disclosure: I'm part of the Linkjob AI team (an AI interview assistant). Free to share.