Algorithm Day89 - Maximum Product Subarray

Posted on In , Views:

🧩 Problem Description

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product, and return the product.

💬 Examples

Example 1

1
2
3
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2

1
2
3
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2 because [-2,-1] is not a contiguous subarray in this case.

💡 Intuition

Because the product of numbers is affected by the sign, a negative number can turn a small (negative) product into a large positive one, and vice versa. Therefore, at each position we need to track both the maximum and minimum product ending at that position.

Let maxF[i] be the maximum product ending at i, and minF[i] the minimum product ending at i. Then:

1
2
maxF[i] = max(nums[i], nums[i] * maxF[i-1], nums[i] * minF[i-1])
minF[i] = min(nums[i], nums[i] * maxF[i-1], nums[i] * minF[i-1])

We can optimize space by keeping only previous max and min values.

🔢 Java Code (DP, O(1) space)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int maxProd = nums[0];
        int minProd = nums[0];
        int ans = nums[0];
        for (int i = 1; i < n; i++) {
            int x = nums[i];
            if (x < 0) { // swap when negative
                int tmp = maxProd;
                maxProd = minProd;
                minProd = tmp;
            }
            maxProd = Math.max(x, maxProd * x);
            minProd = Math.min(x, minProd * x);
            ans = Math.max(ans, maxProd);
        }
        return ans;
    }
}

⏱ Complexity Analysis

  • Time: O(n) — single pass through the array.
  • Space: O(1) — constant extra space.

✍️ Summary

  • Track both maximum and minimum products at each step because negative numbers can flip signs.
  • Swap max/min when encountering a negative number before updating.
  • Keep a running global maximum answer.

Related problems

  • lc-53 — Maximum Subarray (Kadane’s algorithm)
  • lc-918 — Maximum Sum Circular Subarray