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:
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.
Video explanation
Here is the video explaining this method in detail. Please check it out:
Method 1 - Naive
Here is the naive approach:
- Generate All Subarrays:
- Use two nested loops.
- The first loop (
i) starts the subarray. - The second loop (
j) ends the subarray.
- Calculate Product:
- For each subarray, calculate the product of its elements.
- Keep track of the maximum product encountered.
- Return Result:
- Once all subarrays have been processed, the maximum product is returned.
Code
Java
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;
}
}
Python
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
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 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
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;
}
}
Python
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