Kadane’s algorithm is the shortest useful algorithm in the interview canon: three lines, $O(n)$ time, $O(1)$ space, and it answers “what is the largest sum any contiguous subarray can have?” over arrays that contain negative numbers — where a sliding window cannot go.

The whole thing rests on one decision made once per element:

Does the best subarray ending here extend the previous one, or start fresh at me?

If the running sum you inherit is negative, it can only drag you down, so you restart. That is it. Everything else on this page is that idea wearing a different hat.

What you’ll learn

• The extend-or-restart decision, and why it is provably optimal.
• Kadane framed as a one-line DP — which is how you extend it.
• Why the all-negative case breaks a naive implementation.
• The three big variants: product (signs flip), circular (wrap around), and absolute value.
• Three real LeetCode problems solved in the browser: 53, 152, 918.

The cue

The pattern

def max_subarray(nums):
    best = current = nums[0]        # NOT 0 -- see the all-negative note
    for x in nums[1:]:
        current = max(x, current + x)   # restart at x, or extend by x
        best = max(best, current)
    return best
 
 
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # 6  -> [4, -1, 2, 1]
print(max_subarray([-3, -1, -2]))                       # -1 -> [-1]

def max_subarray(nums):
    best = current = nums[0]        # NOT 0 -- see the all-negative note
    for x in nums[1:]:
        current = max(x, current + x)   # restart at x, or extend by x
        best = max(best, current)
    return best
 
 
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # 6  -> [4, -1, 2, 1]
print(max_subarray([-3, -1, -2]))                       # -1 -> [-1]

currentcurrent means the best sum of any subarray ending exactly at this index. bestbest is the best of those over all indices. Two variables, one pass.

Why extend-or-restart is optimal

Let current[i]current[i] be the largest sum of a subarray ending at index ii. Any such subarray either is just nums[i]nums[i], or is a subarray ending at i-1i-1 extended by nums[i]nums[i]. The best of the second kind is current[i-1] + nums[i]current[i-1] + nums[i]. So

$\text{current}[i] = \max\big(\text{nums}[i],\ \text{current}[i-1] + \text{nums}[i]\big)$

and the answer is $\max_i \text{current}[i]$. That is a complete DP, and because current[i]current[i] depends only on current[i-1]current[i-1], the table collapses to one variable — which is why the space is $O(1)$.

Reading it as a DP is what lets you extend it: for the product variant you simply need two rolling states instead of one.

The variant map

Practice — real LeetCode problems

LC 53 — Maximum Subarray · Medium

Problem. Given an integer array numsnums, find the contiguous subarray with at least one element that has the largest sum, and return that sum.

Constraints. 1 <= len(nums) <= 10^51 <= len(nums) <= 10^5, -10^4 <= nums[i] <= 10^4-10^4 <= nums[i] <= 10^4.

Examples. [-2,1,-3,4,-1,2,1,-5,4][-2,1,-3,4,-1,2,1,-5,4] gives 66 ([4,-1,2,1][4,-1,2,1]) · [1][1] gives 11 · [5,4,-1,7,8][5,4,-1,7,8] gives 2323 · [-3,-1,-2][-3,-1,-2] gives -1-1

LC 152 — Maximum Product Subarray · Medium

Problem. Given an integer array numsnums, find the contiguous subarray with the largest product, and return that product.

Constraints. 1 <= len(nums) <= 2 * 10^41 <= len(nums) <= 2 * 10^4, -10 <= nums[i] <= 10-10 <= nums[i] <= 10. The answer fits in a 32-bit integer.

Examples. [2,3,-2,4][2,3,-2,4] gives 66 ([2,3][2,3]) · [-2,0,-1][-2,0,-1] gives 00 · [-2,3,-4][-2,3,-4] gives 2424 (the whole array) · [0,2][0,2] gives 22

LC 918 — Maximum Sum Circular Subarray · Medium

Problem. Given a circular integer array numsnums, return the maximum sum of a non-empty subarray. The subarray may wrap from the end back to the beginning, but may not include any element more than once.

Constraints. 1 <= len(nums) <= 3 * 10^41 <= len(nums) <= 3 * 10^4, -3 * 10^4 <= nums[i] <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4.

Examples. [1,-2,3,-2][1,-2,3,-2] gives 33 · [5,-3,5][5,-3,5] gives 1010 (wraps) · [-3,-2,-3][-3,-2,-3] gives -2-2 · [-2,4,-5,4,-5,9,4][-2,4,-5,4,-5,9,4] gives 1515

LeetCode problem set

Interview follow-ups

Edge-case checklist

• All negative — the headline trap. Answer is the largest single element, not 00.
• Single element — must return that element, even if negative.
• All positive — the answer is the entire array; a sanity check.
• Contains zeros — harmless for sums; the reset case for products.
• Empty subarray allowed? — a real specification question (2606 vs 53); ask rather than assume.
• Wrapping answer covering the whole array (918) — possible when all values are positive; make sure your formula does not exclude everything.
• Two negatives making a positive product (152) — [-2,3,-4][-2,3,-4] gives 2424; the case that catches single-state solutions.

Recap

• Kadane is one decision per element: extend the previous subarray, or restart here — current = max(x, current + x)current = max(x, current + x).
• It is a collapsed DP, which is why it is $O(n)$ time and $O(1)$ space, and why the variants are just “carry more state”.
• Never initialise to 00 unless the empty subarray is explicitly allowed — otherwise all-negative input returns the wrong answer.
• Product needs two states because negatives invert the ordering.
• Circular reframes a wrapping subarray as the contiguous block it excludes: max(best_max, total - best_min)max(best_max, total - best_min), guarded against all-negative input.
• Kadane finds the best subarray; counting subarrays is prefix sums + a hash map instead.

Next: Cyclic Sort — the trick for arrays that are a permutation of 1..n1..n, where the values themselves tell you where they belong.