Kadane's Algorithm —
Maximum subarray in one pass.
Kadane's algorithm finds the contiguous subarray with the largest sum in O(n) — a single left-to-right pass with just two variables. The key decision at every index: is it better to extend the current subarray or start fresh? Watch current_sum and max_sum update at every element on LearnBug and the insight clicks instantly.
What is Kadane's Algorithm?
Kadane's algorithm is a dynamic programming technique that solves the maximum subarray problem in linear time. At each index, you decide: add the current element to the existing subarray sum, or start a new subarray from here? The rule is simple — if current_sum + nums[i] is less than nums[i] alone, start fresh. Track the global maximum throughout and you have your answer in one pass.
Why visualization changes everything
The "start fresh" decision is the part everyone misunderstands. On LearnBug, you watch current_sum accumulate positively, then drop when a large negative arrives, then reset to 0 — and max_sum freezes at the highest value seen so far. The two-variable dance becomes completely clear once you watch it run on a negative-containing array.
Step by step — with negative numbers
Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4] — answer: 6 (subarray [4, -1, 2, 1])
Index 0 — element: -2
Start: current_sum = -2, max_sum = -2. Current is negative — if we see a positive next, starting fresh will be better.
current_sum = -2 | max_sum = -2
Index 1 — element: 1
current_sum = max(-2 + 1, 1) = max(-1, 1) = 1. Start fresh! Carrying -2 would hurt. max_sum = max(-2, 1) = 1.
current_sum = 1 | max_sum = 1
Indices 2–3 — -3 then 4
After -3: current_sum = max(1-3, -3) = -2. After 4: current_sum = max(-2+4, 4) = 4. Start fresh again — the -3 dragged us below zero so we drop it. max_sum = 4.
current_sum = 4 | max_sum = 4
Indices 4–6 — -1, 2, 1 (the winning subarray)
After -1: current = 3. After 2: current = 5. After 1: current = 6. New max! max_sum = 6. This is our answer — subarray [4, -1, 2, 1] sums to 6.
current_sum = 6 | max_sum = 6 ✓ New maximum!
Indices 7–8 — -5, 4 (can't beat 6)
After -5: current = 1. After 4: current = 5. Neither beats 6. Final answer: max_sum = 6.
current_sum = 5 | max_sum = 6 ✓ Final answer
Kadane's in code — two versions
def max_subarray_sum(nums):
current_sum = nums[0]
max_sum = nums[0]
for i in range(1, len(nums)):
# extend current subarray or start fresh from here
current_sum = max(nums[i], current_sum + nums[i])
max_sum = max(max_sum, current_sum)
return max_sumdef max_subarray_with_indices(nums):
current_sum = max_sum = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > current_sum + nums[i]: # start fresh
current_sum = nums[i]
temp_start = i
else:
current_sum += nums[i]
if current_sum > max_sum: # new global max
max_sum = current_sum
start = temp_start
end = i
return max_sum, nums[start:end + 1]Time & Space Complexity
Three edge cases to handle in interviews
All negative numbers
If all elements are negative, the max subarray is a single element — the least negative one. Initialise current_sum = max_sum = nums[0] (not 0) to handle this.
Single element array
Returns that element. Works automatically if you initialise with nums[0] and loop from index 1.
All positive numbers
The entire array is the answer. current_sum never resets to 0 and keeps growing — max_sum ends up as the total sum.
Interviewer asks for the subarray itself
Track temp_start when you reset, and update start / end whenever you find a new max. Return nums[start:end+1].
Frequently asked questions
Why do we initialise current_sum with nums[0] and not 0?
If you initialise with 0, an all-negative array would return 0 — but 0 is not a valid subarray sum (the subarray must contain at least one element). Initialising with nums[0] ensures we always return the actual maximum element even when all elements are negative.
Is Kadane's algorithm dynamic programming?
Yes. The recurrence is dp[i] = max(nums[i], dp[i-1] + nums[i]) where dp[i] is the maximum subarray sum ending at index i. Kadane's is this DP with the O(n) space optimised away — since dp[i] only depends on dp[i-1], you only need one variable (current_sum).
What is the brute force approach and why is it worse?
Brute force tries every pair of start and end indices, computing the subarray sum for each. That's O(n²) pairs × O(n) to sum each = O(n³) naive, or O(n²) with a prefix sum optimisation. Kadane's eliminates the need to consider pairs entirely by making the local decision at each index in O(1).
Can Kadane's algorithm find the maximum product subarray?
Not directly — multiplication by a negative flips the sign, so you need to track both the current maximum and current minimum at every step (a negative × negative becomes the new maximum). The maximum product subarray problem uses a modified version of Kadane's that maintains two running values instead of one.
What LeetCode problems use Kadane's algorithm?
Directly: Maximum Subarray (LC 53). Variants: Maximum Product Subarray (LC 152), Best Time to Buy and Sell Stock (LC 121 — equivalent to max subarray on price differences), Maximum Sum Circular Subarray (LC 918). If you master LC 53 and understand the DP connection, the variants follow naturally.
Watch current_sum and max_sum update on your array
Paste your maximum subarray problem into LearnBug and see Kadane's decide at every index.