Kadane's Algorithm with More State

EditorialUpdated Oct 25, 2026

When one number isn't enough

Maximum Product Subarray: the largest product of a contiguous subarray. Kadane's rule from Kadane's Algorithm, with * in place of +, looks like it should work:

def max_product(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur * x)                   # Kadane's rule, with * for +
        best = max(best, cur)
    return best

On [-2, 3, -4] it returns 3. The answer is 24, the whole array: two negatives make a positive. When the code reached −4, the product ending at 3 was 3 and the best it could do was 3 × −4 = −12, so it started over. The product it needed, −2 × 3 = −6, had already been thrown away: it was the smallest product ending at 3, and a negative value turns the smallest into the largest.

Three values, −2, 3 and −4, in columns. Under each, two pills: the largest and the smallest product of a subarray ending there. At −2 both are −2. At 3 the largest is 3 and the smallest is −6. At −4 two arrows cross: −6 times −4 climbs to the largest, 24, and 3 times −4 drops to the smallest, −12. Keeping only the largest, the best would stop at 3.

Keep the largest and the smallest

So carry two numbers: hi, the largest product of a subarray ending here, and lo, the smallest. The next value x can start fresh, or multiply either one, so both come from the same three candidates: x, hi · x and lo · x. Work out both products from the old hi and lo before changing either.

Zeros need nothing special: they make hi and lo 0, and the next value on its own beats 0 times it whenever it's bigger.

Largest and smallest products of [2, 3, -2, 4, -1] — The highlighted value is the one being multiplied in; the panel shows hi, lo and best after it.

int maxProduct(const vector<int>& nums) {
    int hi = nums[0], lo = nums[0], best = nums[0]; // the largest and smallest product ending here
    for (size_t i = 1; i < nums.size(); i++) {
        int x = nums[i];
        int a = hi * x, b = lo * x;             // both from the products ending just before
        hi = max({x, a, b});                    // a negative x turns the smallest into the largest
        lo = min({x, a, b});
        best = max(best, hi);
    }
    return best;
}

def max_product(nums):
    hi = lo = best = nums[0]                    # the largest and smallest product ending here
    for x in nums[1:]:
        a, b = hi * x, lo * x                   # both from the products ending just before
        hi = max(x, a, b)                       # a negative x turns the smallest into the largest
        lo = min(x, a, b)
        best = max(best, hi)
    return best

static int maxProduct(int[] nums) {
    int hi = nums[0], lo = nums[0], best = nums[0]; // the largest and smallest product ending here
    for (int i = 1; i < nums.length; i++) {
        int x = nums[i];
        int a = hi * x, b = lo * x;             // both from the products ending just before
        hi = Math.max(x, Math.max(a, b));       // a negative x turns the smallest into the largest
        lo = Math.min(x, Math.min(a, b));
        best = Math.max(best, hi);
    }
    return best;
}

function maxProduct(nums) {
    let hi = nums[0], lo = nums[0], best = nums[0]; // the largest and smallest product ending here
    for (let i = 1; i < nums.length; i++) {
        const x = nums[i];
        const a = hi * x, b = lo * x;           // both from the products ending just before
        hi = Math.max(x, a, b);                 // a negative x turns the smallest into the largest
        lo = Math.min(x, a, b);
        best = Math.max(best, hi);
    }
    return best;
}

Each prints 6, 0, 24, -2 and 48 for [2, 3, -2, 4], [-2, 0, -1], [-2, 3, -4], [-2] and [2, 3, -2, 4, -1]. One pass, O(n) time, O(1) space.

One deletion: with and without

Maximum Subarray Sum with One Deletion: the largest sum of a subarray after deleting at most one value from it, keeping at least one. Carry two bests ending here:

none: nothing deleted yet, which is plain Kadane's;
one: exactly one value deleted. Either the deletion happened earlier and x is kept (one + x), or x itself is the one deleted, leaving the best that ended just before it with nothing deleted (none, the old one).

Before the second value there's nothing to delete from, so one starts at minus infinity, not 0:

def maximum_sum(arr):
    none = arr[0]                               # best sum ending here, nothing deleted
    one = float('-inf')                         # best sum ending here, one value deleted: not possible yet
    best = arr[0]
    for x in arr[1:]:
        one = max(one + x, none)                # keep x after an earlier deletion, or delete x itself
        none = max(x, none + x)                 # plain Kadane's, updated after one has read the old value
        best = max(best, none, one)
    return best

It prints 4, 3 and −1 for [1, -2, 0, 3], [1, -2, -2, 3] and [-1, -1, -1, -1]. In the first, deleting −2 joins 1, 0 and 3 into 4.

Alternating signs: up and down

Longest Turbulent Subarray: the longest subarray whose comparisons alternate, up, down, up, ... or down, up, down, .... Carry the longest turbulent run ending here whose last step went up, and the one whose last step went down. An up step extends a run that last went down, and a down step one that last went up; equal neighbours break both:

def max_turbulence_size(arr):
    up = down = best = 1                        # longest turbulent run ending here, last step up / down
    for i in range(1, len(arr)):
        if arr[i] > arr[i - 1]:
            up, down = down + 1, 1              # an up step continues a run whose last step went down
        elif arr[i] < arr[i - 1]:
            up, down = 1, up + 1
        else:
            up = down = 1                       # equal neighbours break every run
        best = max(best, up, down)
    return best

It prints 5, 2 and 1 for [9, 4, 2, 10, 7, 8, 8, 1, 9], [4, 8, 12, 16] and [100].

The pattern in all three: Kadane's carries the best answer ending here. When the next step depends on more than that one number (the sign of the product, whether a deletion is used up, which way the last step went), carry one number for each case, and compute every new one from the old ones.

Spotting it

Look for a best-subarray question with a twist that the next step has to know about:

a product (signs flip): keep the largest and the smallest;
skip, delete or change at most one value: keep the best with it used and unused;
comparisons that must alternate: keep the best ending going up and going down;
a cost to switch between two kinds of moves: keep the best ending in each kind.

The near-miss: if the twist needs the whole history, not a few numbers about it ("no two equal values in the subarray"), a fixed set of states won't do. That's a sliding window or general dynamic programming.

Common mistakes

Updating hi before working out lo. hi = max(...), then lo = min(x, hi * x, lo * x)

lo then multiplies the new hi, not the product that really ended before x. On [-2, 3, -4, -1] it returns 96 instead of 24. Compute hi · x and lo · x first, then assign both.

Starting the deletion state at 0. none = one = 0

Before the first value, "one value deleted" means deleting the only value, an empty subarray. On [-1, -1, -1, -1] it returns 0 instead of −1. Start one at minus infinity.

Updating none before one. none = max(x, none + x) above one = max(one + x, none)

Deleting x must leave the best that ended before x, but none already includes x by then. On [1, -2, 0, 3] it returns 3 instead of 4.

Letting equal neighbours continue a turbulent run. if arr[i] >= arr[i - 1]:

Two equal values aren't an up step. On [9, 9] it returns 2, but no turbulent subarray is longer than 1 there.

Check yourself

Quiz

1 / 6

Multiple choice

Kadane's rule with products, cur = max(x, cur * x), on [-2, 3, -4]. What does it return?

Practice problems

From easier to harder:

Maximum Product Subarray: the largest and the smallest.
Maximum Subarray Sum with One Deletion: with and without a deletion.
Longest Turbulent Subarray: ending up and ending down.

Then the Kadane's Quiz checks the whole section.