In the given problem statement, we have an array of integers and we need to find the maximum product possible for a contiguous subarray.
The most important part of this problem is that the elements have to be contiguous. So special attention needs to be given for negative numbers and zeroes.
Input: nums = [ 2 , 3 , -2 , 4 ] Output: 6 Explanation: [ 2 , 3 ] has the largest product 6.
Input: nums = [ 2 , 3 , -2 , -5 , 6 , -1 , 4 ] Output: 360 Explanation: [ 2 , 3 , -2 , -5 , 6 ] has the largest product 360.
Brute Force Solution
The brute force approach to finding the maximum product subarray involves checking all possible subarrays and calculating their products to find the maximum product.
- Initialize a variable
max_product
to store the maximum product, initially set to the minimum possible value. - Iterate through all possible starting indices of the subarray.
- For each starting index, iterate through all possible ending indices greater than or equal to the starting index.
- Extract the subarray from the starting index to the ending index.
- Calculate the product of all elements in the subarray.
- Update
max_product
if the calculated product is greater than the current maximum. - Repeat steps 3-6 until all possible subarrays are considered.
- Return
max_product
as the maximum product of a subarray within the given array.
This brute force approach has a time complexity of O(n^3), where n is the length of the input array. Since it involves nested loops, it checks every possible subarray combination, making it highly inefficient for large input sizes.
While the brute force solution is straightforward, it is not efficient for solving larger instances of the problem. We need something better.
Efficient Solution
To solve this problem, you can utilize the dynamic programming approach. Here’s a general outline of the solution:
- Initialize two variables,
max_product
andmin_product
, both set to the first element of the array. - Initialize a variable
max_global
to store the overall maximum product. - Iterate through the array starting from the second element.
- For each element, update
max_product
andmin_product
by considering three possibilities: a. Multiply the current element bymax_product
(to include the current element in the positive product chain). b. Multiply the current element bymin_product
(to include the current element in the negative product chain, in case the current element is negative). c. Start a new subarray from the current element (if the previous subarray’s product is not significant). - Update
max_global
by comparing it withmax_product
. - Repeat steps 4-5 until all elements are processed.
- Return
max_global
as the maximum product of a subarray within the given array.
This approach allows you to keep track of both the maximum and minimum product at each step, considering the possibility of negative numbers and the potential of changing the product’s sign.
Code
int maxProduct(int[] nums) {
int n = nums.length;
int leftProduct = 1;
int rightProduct = 1;
int ans = nums[0];
for (int i = 0; i < n; i++) {
//if any of leftProduct or rightProduct become 0 then update it to 1
leftProduct = leftProduct == 0 ? 1 : leftProduct;
rightProduct = rightProduct == 0 ? 1 : rightProduct;
//prefix product
leftProduct *= nums[i];
//suffix product
rightProduct *= nums[n - 1 - i];
ans = Math.max(ans, Math.max(leftProduct, rightProduct));
}
return ans;
}
Code language: Java (java)
Time Complexity: O(n)
Space Complexity: O(n)