Problem

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.

OR

Given an integer array with negative numbers and zero find the subarray with maximum product, i.e. find the contiguous array elements that produce maximum 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 subarray.

Solution

Whenever a 0 appears, it splits the array into separate subarrays. We need to find the maximum product for each of these subarrays and return the largest product. Within each subarray, if there is an even number of negative elements, the maximum product is the product of the entire subarray. If there is an odd number of negative elements, form two subarrays—one excluding the leftmost negative element and the other excluding the rightmost negative element. The larger product of these two will be the result.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive

Here is the naive approach:

  1. Generate All Subarrays:
    • Use two nested loops.
    • The first loop (i) starts the subarray.
    • The second loop (j) ends the subarray.
  2. Calculate Product:
    • For each subarray, calculate the product of its elements.
    • Keep track of the maximum product encountered.
  3. Return Result:
    • Once all subarrays have been processed, the maximum product is returned.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int maxProductNaive(int[] nums) {
        int ans = Integer.MIN_VALUE; // Start with smallest possible value
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            int prod = 1;
            for (int j = i; j < n; j++) {
                prod *= nums[j];
                ans = Math.max(ans, prod);
            }
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def maxProductNaive(self, nums: List[int]) -> int:
        ans: int = float('-inf')  # Start with smallest possible value
        n: int = len(nums)
        
        for i in range(n):
            prod: int = 1
            for j in range(i, n):
                prod *= nums[j]
                ans = max(ans, prod)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n^2) due to nested loops to generate all possible subarrays.
  • 🧺 Space complexity: O(1)

Method 2 - Algo Similar to Kadane’s Algo

This is similar to maximum subarray sum. Instead of sum, the sign of number affect the product value.

We can use maxEndingHere and minEndingHere to keep track of positive and negative product so far. But, wherever there is 0, our product becomes 0. So, we reset these 2 variables. We need to find the maximum product of these subarrays individually and return the largest product.

Inside this subproblem if there are even number of negative elements then maximum product is the complete product of the array. If there are odd number of negative elements, then make two subarrays once leaving the leftmost negative element and once leaving the rightmost negative element. The maximum of these two products will be returned.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;

        // Edge case: When the array is empty
        if (n == 0) {
            return 0;
        }

        // max positive product ending at the current position
        int maxEndingHere = nums[0]; 
        
        // min (negative) product ending at the current position
        int minEndingHere = nums[0]; 
        
        // Initialize overall max product to the first element
        int maxSoFar = nums[0];

        // Traverse through the array, starting from the second element
        for (int i = 1; i < n; i++) {
            int current = nums[i];
            
            // If the current element is negative, swap maxEndingHere and minEndingHere
            if (current < 0) {
                int temp = maxEndingHere;
                maxEndingHere = minEndingHere;
                minEndingHere = temp;
            }
            
            // Update maxEndingHere and minEndingHere
            maxEndingHere = Math.max(current, maxEndingHere * current);
            minEndingHere = Math.min(current, minEndingHere * current);

            // Update the global max product
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Dry run

Consider the array nums = [1, -2, -3, 0, 7, -8, -2].

Initialization

nums[0] = 1, so maxEndingHere = 1 minEndingHere = 1 maxSoFar = 1

Iterations

Step 1 (i = 1, current = -2):

1
2
3
4
5
6
7
8

if (current < 0) { // current is -2
    int temp = maxEndingHere; // temp = 1
    maxEndingHere = minEndingHere; // maxEndingHere = 1
    minEndingHere = temp; // minEndingHere = 1
}
maxEndingHere = Math.max(-2, 1 * -2) = Math.max(-2, -2) = -2
minEndingHere = Math.min(-2, 1 * -2) = Math.min(-2, -2) = -2
maxSoFar = Math.max(1, -2) = 1

Step 2 (i = 2, current = -3):

1
2
3
4
5
6
7
8

if (current < 0) { // current is -3
    int temp = maxEndingHere; // temp = -2
    maxEndingHere = minEndingHere; // maxEndingHere = -2
    minEndingHere = temp; // minEndingHere = -2
}
maxEndingHere = Math.max(-3, -2 * -3) = Math.max(-3, 6) = 6
minEndingHere = Math.min(-3, -2 * -3) = Math.min(-3, 6) = -3
maxSoFar = Math.max(1, 6) = 6

Step 3 (i = 3, current = 0):

1
2
3
4
5

if (current < 0) { // current is 0 (skipped)
}
maxEndingHere = Math.max(0, 6 * 0) = Math.max(0, 0) = 0
minEndingHere = Math.min(0, -3 * 0) = Math.min(0, 0) = 0
maxSoFar = Math.max(6, 0) = 6

Step 4 (i = 4, current = 7):

1
2
3
4
5

if (current < 0) { // current is 7 (skipped)
}
maxEndingHere = Math.max(7, 0 * 7) = Math.max(7, 0) = 7
minEndingHere = Math.min(7, 0 * 7) = Math.min(7, 0) = 0
maxSoFar = Math.max(6, 7) = 7

Step 5 (i = 5, current = -8):

1
2
3
4
5
6
7
8

if (current < 0) { // current is -8
    int temp = maxEndingHere; // temp = 7
    maxEndingHere = minEndingHere; // maxEndingHere = 0
    minEndingHere = temp; // minEndingHere = 7
}
maxEndingHere = Math.max(-8, 0 * -8) = Math.max(-8, 0) = 0
minEndingHere = Math.min(-8, 7 * -8) = Math.min(-8, -56) = -56
maxSoFar = Math.max(7, 0) = 7

Step 6 (i = 6, current = -2):

1
2
3
4
5
6
7
8

if (current < 0) { // current is -2
    int temp = maxEndingHere; // temp = 0
    maxEndingHere = minEndingHere; // maxEndingHere = -56
    minEndingHere = temp; // minEndingHere = 0
}
maxEndingHere = Math.max(-2, -56 * -2) = Math.max(-2, 112) = 112
minEndingHere = Math.min(-2, 0 * -2) = Math.min(-2, 0) = -2
maxSoFar = Math.max(7, 112) = 112

Method 3 - Tracking max and min

At each index i, update the maximum and minimum values. Keeping track of the minimum is crucial because multiplying a negative number with the minimum value can turn it into the maximum, and vice versa. For each index i, calculate the maximum of the i-th element, prevMax multiplied by the i-th element, and prevMin multiplied by the i-th element.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
	public int maxProduct(int nums[]) {	
		int max = nums[0], min = nums[0], ans = nums[0];
		
		for (int i = 1; i<n; i++) {
			int temp = max;  // store the max because before updating min your max will already be updated
			int num = nums[i];
			max = Math.max(Math.max(max * num, min * num), num);
            min = Math.min(Math.min(temp * num, min * num), num);
	
			ans = Math.max(ans, max);
		}
	
		return maxSoFar;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # Initialising variables
        max_product: int = nums[0]
        min_product: int = nums[0]
        ans: int = nums[0]
        
        # Iterating through the array starting from index 1
        for num in nums[1:]:
            temp_max: int = max_product  # Store the current max before updating
            
            # Update max_product and min_product
            max_product = max(
	            num, num * max_product, num * min_product
	        )
            min_product = min(
	            num, num * temp_max, num * min_product
	        )
            
            # Update the final answer
            ans = max(ans, max_product)
        
        return ans