Problem

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:

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.

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.

Method 1 - 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

Java
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):

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):

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):

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):

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):

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):

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 2 - 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

Java
```java
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;
	}
}

Method 3 - Track min and max arrays

The idea is to traverse array from left to right keeping two arrays min and max which represents the minimum and maximum product value till the ith index of the array.

Code

Java
public int maxProduct(int[] nums) {
	int[] max = new int[nums.length];
	int[] min = new int[nums.length];

	max[0] = min[0] = nums[0];
	int result = nums[0];

	for (int i = 1; i<nums.length; i++) {
		if (nums[i] > 0) {
			max[i] = Math.max(nums[i], max[i - 1] * nums[i]);
			min[i] = Math.min(nums[i], min[i - 1] * nums[i]);
		} else {
			max[i] = Math.max(nums[i], min[i - 1] * nums[i]);
			min[i] = Math.min(nums[i], max[i - 1] * nums[i]);
		}

		result = Math.max(result, max[i]);
	}

	return result;
}

Complexity

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