Maximum Product Subarray (LC 152)

Pattern: Array / Dynamic Tracking of Min & Max
Difficulty: Medium
Key Concept: A negative number can turn a small (most negative) running product into the largest product, so track both the max and min product ending at each index.

Problem Statement

Given an integer array nums, find a contiguous non-empty subarray that has the largest product, and return that product.

Input

• nums — integer array

Output

• int — maximum product over all contiguous non-empty subarrays

Example

• nums = [2, 3, -2, 4] → 6 (subarray [2, 3]).

---

1. Algorithm & Pseudocode

Brute force

1. Set best to nums[0].
2. For each start i from 0 to n - 1:
3. Set prod = 1.
4. For each end j from i to n - 1:
5. Multiply: prod = prod * nums[j].
6. If prod > best, set best = prod.
7. Return best.

Optimal

1. Initialize maxSoFar = minSoFar = best = nums[0].
2. For k from 1 to n - 1:
3. Let x = nums[k].
4. If x < 0, swap maxSoFar and minSoFar (because multiplying flips order: large×negative becomes small, small×negative becomes large).
5. Update maxSoFar = max(x, maxSoFar * x).
6. Update minSoFar = min(x, minSoFar * x).
7. best = max(best, maxSoFar).
8. Return best.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why brute force is correct
Every contiguous subarray is tried; products are exact (within Java int range—LeetCode assumes results fit in 32-bit signed int).

Why brute force is slow
(O(n^2)) subarrays—too slow for large (n).

Why “max only” (like Kadane for sum) fails
Multiplication by a negative flips the sign. A running product that looks terrible (very negative) can become the best after one more negative number. Example: in [-2, 3, -4], the subarray [-2, 3, -4] has product 24, which you only discover if you remember that -2 * 3 = -6 was a useful “small” intermediate, not just garbage to discard forever.

Why track minSoFar
minSoFar holds the smallest (most negative) product ending here. When x is negative, minSoFar * x can become a huge positive candidate for the answer.

Why swap on negative x
Multiplying both running extremes by a negative reverses their ordering: the old max becomes the “more negative” chain and the old min becomes the “more positive” chain. Swapping aligns variables so the same max(x, prevMax * x) formulas still work.

ASCII — sign flip intuition

...  maxSoFar = 6, minSoFar = -2, next x = -3

Without care: 6 * -3 = -18, (-2) * -3 = 6  ← the "min" path wins

After swap (conceptually): treat the old min as the chain that extends to large positive after * negative

---

3. The Dry Run

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

k	x	swap?	maxSoFar after	minSoFar after	best
0	2	—	2	2	2
1	3	no	max(3,6)=6	min(3,6)=3	6
2	-2	yes	max(-2,-6)=-2	min(-2,-12)=-12	6
3	4	no	max(4,-8)=4	min(4,-48)=-48	6

Result: 6.

Zeros: When x == 0, the updates maxSoFar = max(0, …) and minSoFar = min(0, …) effectively reset the running product chain to 0, which matches “start a new subarray here.” LeetCode’s tests include zeros; the listed optimal code handles them without a separate branch.

---

4. Java Solution

Brute Force

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int best = nums[0];
        for (int i = 0; i < n; i++) {
            int prod = 1;
            for (int j = i; j < n; j++) {
                prod *= nums[j];
                if (prod > best) {
                    best = prod;
                }
            }
        }
        return best;
    }
}

Time: (O(n^2)).
Space: (O(1)).

Optimal

class Solution {
    public int maxProduct(int[] nums) {
        int maxSoFar = nums[0];
        int minSoFar = nums[0];
        int best = nums[0];

        for (int k = 1; k < nums.length; k++) {
            int x = nums[k];
            if (x < 0) {
                int tmp = maxSoFar;
                maxSoFar = minSoFar;
                minSoFar = tmp;
            }
            maxSoFar = Math.max(x, maxSoFar * x);
            minSoFar = Math.min(x, minSoFar * x);
            best = Math.max(best, maxSoFar);
        }
        return best;
    }
}

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

Note: The swap-on-negative formulation assumes maxSoFar and minSoFar already summarize the previous step; when x == 0, maxSoFar * x and minSoFar * x are both 0, and max(0,0)=0, min(0,0)=0, so the chain resets naturally—best still updates via max(best, 0) when zeros appear. Verify with nums = [-2, 0, -1].

---

5. The “Java vs. Others” Edge

• Math.max / Math.min on int avoid importing anything else; no long needed unless you extend to “product fits in long.”
• Swapping with a temporary int is clear and avoids XOR tricks on signed values.
• Unlike sum Kadane, watch integer overflow in interviews; LeetCode 152 stays within int by problem guarantee.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n^2))	(O(1))	Enumerates all subarrays.
Optimal	(O(n))	(O(1))	Tracks max/min product ending at each index.