On this page
Description
Kadane's algorithm finds the maximum-sum subarray by keeping one running value. At each element, it either extends the best subarray ending just before, or starts fresh. That works because adding the same number to two running sums never changes which one is larger. Change the operation or the shape and that single value isn't enough anymore. With products, a large negative can flip into the best answer. With a circular array, the best subarray can wrap around the end. This skill covers the extra state each variant needs, while keeping the single O(n) pass.
We'll go from simple to more technical:
- The pattern: maximum product, tracking both a running max and a running min.
- A second flavor: circular arrays, using the total minus the smallest middle part.
- Where streak-style DP shows up in production.
- What breaks it: a missing min, the all-negative case, and overflow.
The approach
Java
int maxProduct(int[] nums) {
int best = nums[0], curMax = nums[0], curMin = nums[0]; // best and worst product ENDING here
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
if (x < 0) { int t = curMax; curMax = curMin; curMin = t; } // a negative flips best and worst
curMax = Math.max(x, curMax * x); // extend, or start fresh at x
curMin = Math.min(x, curMin * x);
best = Math.max(best, curMax);
}
return best;
}
Python
def max_product(nums: list[int]) -> int:
best = cur_max = cur_min = nums[0] # best and worst product ENDING here
for x in nums[1:]:
if x < 0:
cur_max, cur_min = cur_min, cur_max # a negative flips best and worst
cur_max = max(x, cur_max * x) # extend, or start fresh at x
cur_min = min(x, cur_min * x)
best = max(best, cur_max)
return best
Multiplying by a negative turns the most negative product into the largest one, so the algorithm keeps both extremes ending at each position and swaps them when x is negative. On [-2, 3, -4], tracking only the maximum gives 3; tracking both finds -2 * 3 * -4 = 24. Zeros are handled by "start fresh at x": a product that hits 0 restarts at the next element.
A second flavor: subarrays that wrap around
In a circular array, a subarray may run off the end and continue at the start. A wrapping subarray is everything except some contiguous middle part - so its best sum is the total minus the smallest middle subarray, which is Kadane run for the minimum:
Java
int total = 0, curMax = 0, bestMax = Integer.MIN_VALUE, curMin = 0, bestMin = Integer.MAX_VALUE;
for (int x : nums) {
total += x;
curMax = Math.max(x, curMax + x); bestMax = Math.max(bestMax, curMax);
curMin = Math.min(x, curMin + x); bestMin = Math.min(bestMin, curMin);
}
if (bestMax < 0) return bestMax; // all negative: the "complement" would be empty
return Math.max(bestMax, total - bestMin);
Python
def max_subarray_sum_circular(nums: list[int]) -> int:
total = cur_max = cur_min = 0
best_max, best_min = float("-inf"), float("inf")
for x in nums:
total += x
cur_max = max(x, cur_max + x)
best_max = max(best_max, cur_max)
cur_min = min(x, cur_min + x)
best_min = min(best_min, cur_min)
if best_max < 0:
return best_max # all negative: the "complement" would be empty
return max(best_max, total - best_min)
The all-negative check matters: for [-3, -2, -3], the smallest middle part is the whole array, and total - bestMin = 0 describes the empty subarray, which isn't allowed. The answer is -2.
Where you'll see it
Signal and time-series analysis looks for the strongest contiguous window (the best stretch of returns, the highest-gain run of readings), and periodic data - hours of a day, days of a week - makes windows wrap around. Compounded growth rates multiply rather than add, which is where the min/max tracking of the product version applies.
Which tool for which job?
| You need | Use |
|---|---|
| Maximum-sum subarray | Kadane: extend or restart |
| Maximum-product subarray | running max and min, swapped on a negative |
| A cross-check for products | best prefix or suffix product per zero-free segment |
| Maximum sum in a circular array | max(Kadane max, total - Kadane min), unless all negative |
| Maximum sum with at most one element deleted | two states: nothing deleted yet, one deleted |
| Maximum-sum rectangle in a matrix | Kadane over the column sums of each row pair |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Tracking only the running max for products | [-2, 3, -4] gives 3 instead of 24 | track the min too, and swap on a negative |
| No all-negative check in the circular version | returns 0, the empty subarray | return the max element when it's negative |
Assuming products fit a long | 10^20 wraps to 7766279631452241920 | rely on the problem's bound, or use logs |
| Products of doubles | 10^400 becomes Infinity | compare sums of logarithms |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why does the maximum product subarray need a running minimum as well as a running maximum?
Show answer
A negative number turns the most negative running product into the largest. On [-2, 3, -4], the product ending at 3 has minimum -6; multiplying by -4 gives 24, the answer. Tracking only the maximum (3) loses that.
2. How can the best wrapping subarray be found without trying every start and length?
Show answer
A wrapping subarray is the whole array minus a contiguous middle part. Its best sum is total minus the minimum subarray sum (Kadane for the minimum). Compare it with the normal maximum subarray and take the larger.
3. For [-3, -2, -3], the circular formula gives total - minSubarray = 0. Why is that wrong?
Show answer
The minimum subarray is the whole array, so its complement is empty - and the problem requires a non-empty subarray. When the normal maximum is negative (every element is negative), return it directly: -2.
Key takeaways
- Kadane keeps the best subarray ending at each position: extend it or start fresh.
- For products, keep the best and worst ending here and swap them on a negative.
- A wrapping subarray is the complement of a middle one: total - minimum subarray.
- Guard the all-negative case - the complement of everything is empty.
- Still O(n) time and O(1) space.