Approach

Maximum Product Subarray

Problem Statement

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

The test cases are generated so that the answer will fit in a 32-bit integer.

Examples

Example 1:

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

Example 2:

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

Constraints

1 ≤ nums.length ≤ 2 * 10^4
-10 ≤ nums[i] ≤ 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Approach

Key Insight

Track both max and min products!

Why? Because a negative number can turn:

Small negative → Large positive (if multiplied by negative)
Large positive → Small negative (if multiplied by negative)

Solution 1: Dynamic Programming

Track max and min at each position.

Algorithm:

Initialize max_prod = min_prod = result = nums[0]
For each element from index 1:
- If negative, swap max_prod and min_prod
- max_prod = max(num, max_prod × num)
- min_prod = min(num, min_prod × num)
- result = max(result, max_prod)
Return result

Solution 2: Kadane's Algorithm Variant

Similar to max subarray sum but track min too.

Algorithm:

Keep track of current_max and current_min
For each number:
- temp_max = max(num, current_max × num, current_min × num)
- current_min = min(num, current_max × num, current_min × num)
- current_max = temp_max
- Update global_max
Return global_max

Solution 3: Two Pass (Forward and Backward)

Scan array twice.

Algorithm:

Forward scan: track running product, reset on zero
Backward scan: track running product, reset on zero
Return max of both scans

Complexity Analysis

DP Solution:

Time Complexity: O(n) - single pass
Space Complexity: O(1) - only variables

Two Pass:

Time Complexity: O(n) - two passes
Space Complexity: O(1) - only variables

Pattern Recognition

This problem demonstrates:

Dynamic Programming with state tracking
Kadane's algorithm variant
Track both max and min pattern
Negative number handling
Similar to Maximum Subarray but with multiplication

Solution

java

1class Solution {
2    // Solution 1: Dynamic Programming (Track Max and Min)
3    public int maxProduct(int[] nums) {
4        if (nums.length == 0) return 0;
5
6        int maxProd = nums[0];
7        int minProd = nums[0];
8        int result = nums[0];
9
10        for (int i = 1; i < nums.length; i++) {
11            int num = nums[i];
12
13            // If negative, swap max and min
14            if (num < 0) {
15                int temp = maxProd;
16                maxProd = minProd;
17                minProd = temp;
18            }
19
20            // Update max and min products
21            maxProd = Math.max(num, maxProd * num);
22            minProd = Math.min(num, minProd * num);
23
24            // Update result
25            result = Math.max(result, maxProd);
26        }
27
28        return result;
29    }
30
31    // Solution 2: Kadane's Variant (Without Swap)
32    public int maxProductKadane(int[] nums) {
33        if (nums.length == 0) return 0;
34
35        int currentMax = nums[0];
36        int currentMin = nums[0];
37        int globalMax = nums[0];
38
39        for (int i = 1; i < nums.length; i++) {
40            int num = nums[i];
41
42            // Calculate all possibilities
43            int tempMax = Math.max(num, Math.max(currentMax * num, currentMin * num));
44            currentMin = Math.min(num, Math.min(currentMax * num, currentMin * num));
45            currentMax = tempMax;
46
47            globalMax = Math.max(globalMax, currentMax);
48        }
49
50        return globalMax;
51    }
52
53    // Solution 3: Two Pass (Forward and Backward)
54    public int maxProductTwoPass(int[] nums) {
55        if (nums.length == 0) return 0;
56
57        int result = nums[0];
58
59        // Forward pass
60        int product = 1;
61        for (int num : nums) {
62            product *= num;
63            result = Math.max(result, product);
64            if (product == 0) {
65                product = 1;
66            }
67        }
68
69        // Backward pass
70        product = 1;
71        for (int i = nums.length - 1; i >= 0; i--) {
72            product *= nums[i];
73            result = Math.max(result, product);
74            if (product == 0) {
75                product = 1;
76            }
77        }
78
79        return result;
80    }
81
82    // Solution 4: Clean DP
83    public int maxProductClean(int[] nums) {
84        int maxSoFar = nums[0];
85        int minSoFar = nums[0];
86        int result = nums[0];
87
88        for (int i = 1; i < nums.length; i++) {
89            int num = nums[i];
90
91            // Store max before updating
92            int temp = maxSoFar;
93
94            // Update max: either start fresh or extend previous
95            maxSoFar = Math.max(num, Math.max(maxSoFar * num, minSoFar * num));
96
97            // Update min: either start fresh or extend previous
98            minSoFar = Math.min(num, Math.min(temp * num, minSoFar * num));
99
100            // Update result
101            result = Math.max(result, maxSoFar);
102        }
103
104        return result;
105    }
106}
107