Largest Product of Any Contiguous Subarray

Given an array nums that may contain negative numbers and zeros, find the largest product achievable by any non-empty contiguous subarray. The tricky part is negatives: a very negative running product can flip into the best possible product the moment it's multiplied by another negative. Plain Kadane's algorithm only tracks a running maximum — here you need to also track a running minimum, since today's worst product might become tomorrow's best one. Whenever the next number is negative, swap the running max and min before extending them — that's what makes the O(n) Kadane's Algorithm variant work for products instead of just sums.

Test Case 1:

Input:nums = [-2, 3, -4]

Output:24

Explanation:The whole array: -2 × 3 × -4 = 24 — both negatives cancel out into a positive.

Test Case 2:

Input:nums = [2, 3, -2, 4]

Output:6

Explanation:The subarray [2, 3] has the largest product; extending further brings in a negative and shrinks it.

Test Case 3:

Input:nums = [0, 2]

Output:2

Explanation:The 0 breaks the array into two pieces — the best product among them is just 2.

Constraints

◆1 ≤ nums.length ≤ 2×10⁴
◆-10 ≤ nums[i] ≤ 10

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 3-8 integers, -6 to 6

1	class Solution {
2	public int maxProductSubarray(int[] nums) {
3	int maxProduct = nums[0];
4	int curMax = nums[0], curMin = nums[0];
5	for (int i = 1; i < nums.length; i++) {
6	int num = nums[i];
7	if (num < 0) {
8	int temp = curMax;
9	curMax = curMin;
10	curMin = temp;
11	}
12	curMax = Math.max(num, curMax * num);
13	curMin = Math.min(num, curMin * num);
14	maxProduct = Math.max(maxProduct, curMax);
15	}
16	return maxProduct;
17	}
18	}
19

-2

3

-4

0

1

2

↑i

Variables

maxProduct-2

curMax-2

curMin-2

INITIALIZE

Start curMax, curMin, and maxProduct all at nums[0] = -2.

Step 1 / 7

Approach & Solutions

Brute Force

Brute

For every possible starting index, multiply forward one element at a time and keep the best product seen. Correct, but re-multiplying from scratch for every subarray wastes the fact that consecutive subarrays share almost all of their elements.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int maxProductSubarray(int[] nums) {
        int maxProduct = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int product = 1;
            for (int j = i; j < nums.length; j++) {
                product *= nums[j];
                maxProduct = Math.max(maxProduct, product);
            }
        }
        return maxProduct;
    }
}

Optimal — Kadane's Algorithm (Track Max and Min)

Optimal

A variant of Kadane's algorithm adapted for multiplication. Unlike sums, a very negative running product can become the best product if multiplied by another negative — so track both a running max and a running min ending at each position. Whenever the current number is negative, swap max and min first, since multiplying by a negative flips which one is more extreme.

TimeO(n)