Problem Statement: Given an array that contains both negative and positive integers, find the maximum product subarray.
Examples:
Example 1: Input: Nums = [1,2,3,4,5,0] Output: 120 Explanation: In the given array, we can see 1×2×3×4×5 gives maximum product value. Example 2: Input: Nums = [1,2,-3,0,-4,-5] Output: 20 Explanation: In the given array, we can see (-4)×(-5) gives maximum product value.
Solution: Brute Force
Approach:
Find all possible subarrays of the given array. Find the product of each subarray. Return the maximum of all them.
Following are the steps for the approach:-
- Run a loop on the array to choose the start point for each subarray.
- Run a nested loop to get the end point for each subarray.
- Multiply elements present in the chosen range.
Dry Run:
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
int maxProductSubArray(vector<int>& nums) {
int result = INT_MIN;
for(int i=0;i<nums.size()-1;i++) {
for(int j=i+1;j<nums.size();j++) {
int prod = 1;
for(int k=i;k<=j;k++)
prod *= nums[k];
result = max(result,prod);
}
}
return result;
}
int main() {
vector<int> nums = {1,2,-3,0,-4,-5};
cout<<"The maximum product subarray: "<<maxProductSubArray(nums);
return 0;
}
Output: The maximum product subarray: 20
Time Complexity: O(N3)
Reason: We are using 3 nested loops for finding all possible subarrays and their product.
Space Complexity: O(1)
Reason: No extra data structure was used
Java Code
import java.util.*;
public class Main
{
static int maxProductSubArray(int arr[]) {
int result = Integer.MIN_VALUE;
for(int i=0;i<arr.length-1;i++)
for(int j=i+1;j<arr.length;j++) {
int prod = 1;
for(int k=i;k<=j;k++)
prod *= arr[k];
result = Math.max(result,prod);
}
return result;
}
public static void main(String[] args) {
int nums[] = {1,2,-3,0,-4,-5};
int answer = maxProductSubArray(nums);
System.out.print("The maximum product subarray is: "+answer);
}
}
Output: The maximum product subarray: 20
Time Complexity: O(N3)
Reason: We are using 3 nested loops for finding all possible subarrays and their product.
Space Complexity: O(1)
Reason: No extra data structure was used
Solution: Optimised Brute Force
Approach:
We can optimize the brute force by making 3 nested iterations to 2 nested iterations
Following are the steps for the approach:
- Run a loop to find the start of the subarrays.
- Run another nested loop
- Multiply each element and store the maximum value of all the subarray.
Dry Run:
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
int maxProductSubArray(vector<int>& nums) {
int result = nums[0];
for(int i=0;i<nums.size()-1;i++) {
int p = nums[i];
for(int j=i+1;j<nums.size();j++) {
result = max(result,p);
p *= nums[j];
}
result = max(result,p);//manages (n-1)th term
}
return result;
}
int main() {
vector<int> nums = {1,2,-3,0,-4,-5};
cout<<"The maximum product subarray: "<<maxProductSubArray(nums);
return 0;
}
Output: The maximum product subarray: 20
Time Complexity: O(N2)
Reason: We are using two nested loops
Space Complexity: O(1)
Reason: No extra data structures are used for computation
Java Code
import java.util.*;
public class Main
{
static int maxProductSubArray(int arr[]) {
int result = arr[0];
for(int i=0;i<arr.length-1;i++) {
int p = arr[i];
for(int j=i+1;j<arr.length;j++) {
result = Math.max(result,p);
p *= arr[j];
}
result = Math.max(result,p);
}
return result;
}
public static void main(String[] args) {
int nums[] = {1,2,-3,0,-4,-5};
int answer = maxProductSubArray(nums);
System.out.print("The maximum product subarray is: "+answer);
}
}
Output: The maximum product subarray: 20
Time Complexity: O(N2)
Reason: We are using two nested loops
Space Complexity: O(1)
Reason: No extra data structures are used for computation
Solution: Two Traversals
Approach:
Idea is to find the maximum product from both sides,i.e, once in a forwarding direction and another in the backward direction.
Following are the steps for the approach:
- Iteration from left to right once to get maximum product for forward direction.
- If zero is encountered, we set all variables again to initial value.
- Iteration from right to left once again to get maximum product for backward direction.
- If zero is encountered, we set all variables again to zero to find a new subarray with maximum product.
- Once both iterations are completed, the overall result for the maximum product subarray of the given array is the maximum product obtained from both the iterations.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
int maxProductSubArray(vector<int>& nums) {
int maxLeft = nums[0];
int maxRight = nums[0];
int prod = 1;
bool zeroPresent = false;
for(auto i:nums) {
prod *= i;
if(i == 0) {
zeroPresent = true;
prod = 1;
continue;
}
maxLeft = max(maxLeft,prod);
}
prod = 1;
for(int j=nums.size()-1;j>=0;j--) {
prod *= nums[j];
if(nums[j] == 0) {
zeroPresent = true;
prod = 1;
continue;
}
maxRight = max(maxRight,prod);
}
if(zeroPresent) return max(max(maxLeft,maxRight),0);
return max(maxLeft,maxRight);
}
int main() {
vector<int> nums = {1,2,-3,0,-4,-5};
cout<<"The maximum product subarray: "<<maxProductSubArray(nums);
return 0;
}
Output: The maximum product subarray: 20
Time Complexity: O(N)
Reason: O(N) iteration two times for computing maximum product.
Space Complexity: O(1)
Reason: No extra data structures are used for computation.
Java Code
import java.util.*;
public class Main
{
static int maxProductSubArray(int arr[]) {
int maxLeft = arr[0];
int maxRight = arr[0];
boolean zeroPresent = false;
int prod = 1;
for(int i:arr) {
prod *= i;
if(i == 0) {
zeroPresent = true;
prod = 1;
continue;
}
maxLeft = Math.max(maxLeft,prod);
}
prod = 1;
for(int j=arr.length-1;j>=0;j--) {
prod *= arr[j];
if(arr[j] == 0) {
zeroPresent = true;
prod = 1;
continue;
}
maxRight = Math.max(maxRight,prod);
}
if(zeroPresent) return Math.max(Math.max(maxLeft,maxRight),0);
return Math.max(maxLeft,maxRight);
}
public static void main(String[] args) {
int nums[] = {1,2,-3,0,-4,-5};
int answer = maxProductSubArray(nums);
System.out.print("The maximum product subarray is: "+answer);
}
}
Output: The maximum product subarray: 20
Time Complexity: O(N)
Reason: O(N) iteration two times for computing maximum product.
Space Complexity: O(1)
Reason: No extra data structures are used for computation.
Solution: Kadane’s Algorithm
Approach:
The following approach is motivated by Kandane’s algorithm. To know Kadane’s Algorithm follow Kadane’s Algorithm
The pick point for this problem is that we can get the maximum product from the product of two negative numbers too.
Following are the steps for the approach:
- Initially store 0th index value in prod1, prod2 and result.
- Traverse the array from 1st index.
- For each element, update prod1 and prod2.
- Prod1 is maximum of current element, product of current element and prod1, product of current element and prod2
- Prod2 is minimum of current element, product of current element and prod1, product of current element and prod2
- Return maximum of result and prod1
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
int maxProductSubArray(vector<int>& nums) {
int prod1 = nums[0],prod2 = nums[0],result = nums[0];
for(int i=1;i<nums.size();i++) {
int temp = max({nums[i],prod1*nums[i],prod2*nums[i]});
prod2 = min({nums[i],prod1*nums[i],prod2*nums[i]});
prod1 = temp;
result = max(result,prod1);
}
return result;
}
int main() {
vector<int> nums = {1,2,-3,0,-4,-5};
cout<<"The maximum product subarray: "<<maxProductSubArray(nums);
return 0;
}
Output: The maximum product subarray: 20
Time Complexity: O(N)
Reason: A single iteration is used.
Space Complexity: O(1)
Reason: No extra data structure is used for computation
Java Code
import java.util.*;
public class Main
{
static int maxProductSubArray(int arr[]) {
int prod1 = arr[0],prod2 = arr[0],result = arr[0];
for(int i=1;i<arr.length;i++) {
int temp = Math.max(arr[i],Math.max(prod1*arr[i],prod2*arr[i]));
prod2 = Math.min(arr[i],Math.min(prod1*arr[i],prod2*arr[i]));
prod1 = temp;
result = Math.max(result,prod1);
}
return result;
}
public static void main(String[] args) {
int nums[] = {1,2,-3,0,-4,-5};
int answer = maxProductSubArray(nums);
System.out.print("The maximum product subarray is: "+answer);
}
}
Output: The maximum product subarray: 20
Time Complexity: O(N)
Reason: A single iteration is used.
Space Complexity: O(1)
Reason: No extra data structure is used for computation
Special thanks to Dewanshi Paul for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article