Maximum Product Subarray

Given an array of integers, find the contiguous subarray with the largest product and return that product.

MediumMust DoKadane's Algorithm

Solve This Problem

Video Solution

Video coming soon

We're producing a video walkthrough — check back soon.

Problem Overview

Given an array of integers, find the contiguous subarray with the largest product and return that product.

Why solve this?

Kadane's algorithm for sums breaks the moment you switch to products — this problem forces you to track both a running maximum AND a running minimum, since multiplying by a negative number can flip the smallest product into the largest.

Pattern Recognition

Whenever a running-aggregate problem involves multiplication (or any operation where sign flips matter) rather than addition, check whether the single running best-so-far needs to become a pair — a running best AND a running worst.

Prerequisites

Maximum Subarray — the running-aggregate shape is identical, but products need two tracked values instead of one, since a negative number can turn the smallest running product into the largest.

Hints

Tracking only a running maximum product fails the moment a negative number appears in the middle of a good run.
Also track a running minimum product — a large negative number times a new negative number becomes a large positive one.
At each element, compute the three candidates (element alone, element * previous max, element * previous min) and let the new max/min be the largest/smallest of those three.

Approach

Track two running values at each index: currentMax, the largest product of a subarray ending here, and currentMin, the smallest (most negative) product of a subarray ending here. At each new element, because multiplying by a negative number swaps which of currentMax/currentMin would produce the larger result, compute both candidateMax = max(num, currentMax * num, currentMin * num) and candidateMin = min(num, currentMax * num, currentMin * num) before overwriting either — using the previous values for both computations, never a value already updated in the same step. The answer is the largest currentMax seen across the whole scan.

Code

Solution.java

class Solution {
    public int maxProduct(int[] nums) {
        int currentMax = nums[0], currentMin = nums[0], result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            int candidateMax = Math.max(num, Math.max(currentMax * num, currentMin * num));
            int candidateMin = Math.min(num, Math.min(currentMax * num, currentMin * num));
            currentMax = candidateMax;
            currentMin = candidateMin;
            result = Math.max(result, currentMax);
        }
        return result;
    }
}

Time: O(n)Space: O(1)