Kadane's / Subarray

Max Product Subarray

Like Kadane's but with multiplication. The twist: a negative × negative = positive, so track BOTH the current max and current min product. A big negative min can become the new max with one more negative number.

O(n)

O(1)

How It Works

Maximum product subarray adapts Kadane's idea to multiplication, where signs complicate everything: a large negative product becomes a large positive one after meeting another negative number. The fix is to carry two running values — the maximum and the minimum product of subarrays ending at the current index. Each step considers three candidates: the element alone, element times previous max, and element times previous min.

When the current element is negative, the previous min (most negative) times it may become the new max, which is why both extremes must be tracked. The scan remains O(n) time and O(1) space, versus O(n²) for checking every subarray, and zeros naturally reset both trackers since any product through zero collapses.

Step-by-Step Visualization

Track max and min product simultaneously

-2

MaxProd2

MinProd2

Result2

1/5

Code

Java

static int maxProduct(int[] nums) {
  int maxProd = nums[0], minProd = nums[0], result = nums[0];

  for (int i = 1; i < nums.length; i++) {
    if (nums[i] < 0) { int tmp = maxProd; maxProd = minProd; minProd = tmp; }
    maxProd = Math.max(nums[i], maxProd * nums[i]);
    minProd = Math.min(nums[i], minProd * nums[i]);
    result = Math.max(result, maxProd);
  }

  return result;
}

// Example: maxProduct(new int[]{2,3,-2,4}) → 6

Tips & Gotchas

1Track both max and min products (a negative min can become max)

2When you encounter 0, reset both to 1

3Negative × negative = positive, so min product matters

Practice Problems

1Maximum Product Subarray
2Maximum Product of Three Numbers
3Subarray Product Less Than K

About the Kadane's / Subarray Pattern

At each position, decide: should I extend the previous subarray, or start fresh here? Track the running sum and the global maximum. This elegant approach finds the maximum subarray sum in O(n).

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

Two Sum
Best Time to Buy & Sell Stock
Maximum Subarray
Merge Intervals
Product of Array Except Self
Container With Most Water

Frequently Asked Questions

Why does the product version need a running minimum when the sum version doesn't?

Addition preserves order — adding a value shifts every sum equally — so only the max matters. Multiplication by a negative number reverses order, turning the smallest product into the largest, so discarding the minimum would throw away future maximums.

How do zeros affect the algorithm?

A zero annihilates any product passing through it, so both running max and min effectively restart at that point. The three-candidate formula handles this automatically because the element alone (0) beats any negative continuation, and the next element then starts fresh.