Max Product Subarray — Kadane's Variant

What does it solve?

Find the contiguous subarray with the largest product. Plain Kadane's (for sums) breaks here: a big negative times another negative becomes a big positive, so the smallest running value can suddenly become the best.

Key insight: carry both the max and min product ending here. When the current number is negative, swap them first, because multiplying flips the ordering. One pass, O(N) time, constant space.

The core idea

// track max & min ending here
maxP = minP = ans = nums[0]
for x in nums[1:]:
  if x < 0: swap(maxP, minP)
  maxP = max(x, maxP * x)
  minP = min(x, minP * x)
  ans = max(ans, maxP)

Complexity

Time complexity

O(N)

A single pass. Each step is a swap, two multiplications, and two comparisons — all O(1).

Space complexity

O(1)

Only maxP, minP, and ans are kept. No auxiliary array needed.

Examples & edge cases

Live animation — dual max/min running products

current element negative → swap best subarray end

Array — scanning left to right

running products ending at i

maxP (largest)

—

minP (smallest)

—

i = — maxP = — minP = — ans = —

Step — of —

index i

—

current element

maxP ending here

—

best positive run

minP ending here

—

most negative run

Best product

—

global answer

Select an example and press Play to start.

✓ Answer: —

Speed Medium

Step-by-step table

Step	i	num	swap?	maxP	minP	ans

C++ implementation

max_product_subarray.cpp

#include <bits/stdc++.h>
using namespace std;

// Maximum product of a contiguous subarray
int maxProduct(vector<int>& nums) {
    int maxP = nums[0], minP = nums[0], ans = nums[0];

    for (int i = 1; i < (int)nums.size(); i++) {
        int x = nums[i];
        // a negative flips which extreme is largest
        if (x < 0) swap(maxP, minP);

        maxP = max(x, maxP * x);   // extend or restart
        minP = min(x, minP * x);

        ans = max(ans, maxP);
    }
    return ans;
}

int main() {
    vector<int> nums = {2, 3, -2, 4};
    cout << maxProduct(nums) << "\n"; // 6
    return 0;
}

My Notes

📝Notes✅

▼

●Start typing to save... 0 chars