Maximum Product Subarray using Traversal From Starting and End of an Array
We will follow a simple approach that is to traverse and multiply elements and if our value is greater than the previously stored value then store this value in place of the previously stored value. If we encounter “0” then make products of all elements till now equal to 1 because from the next element, we will start a new subarray.
But what can be the problem with that?
Problem will occur when our array will contain odd no. of negative elements. In that case, we have to reject anyone negative element so that we can even no. of negative elements and their product can be positive. Now since we are considering subarray so we can’t simply reject any one negative element. We have to either reject the first negative element or the last negative element.
But if we will traverse from starting then only the last negative element can be rejected and if we traverse from the last then the first negative element can be rejected. So we will traverse from both the end and from both the traversal we will take answer from that traversal only which will give maximum product subarray.
So actually we will reject that negative element whose rejection will give us the maximum product’s subarray.
Below is the implementation of the above approach:
// C++ program to find Maximum Product Subarray
#include <bits/stdc++.h>
using namespace std;
/* Returns the product
of max product subarray. */
long long int maxSubarrayProduct(int arr[], int n)
{
long long ans = INT_MIN;
// leftToRight to store product from left to Right
long long leftToRight = 1;
// rightToLeft to store product from right to left
long long rightToLeft = 1;
for (int i = 0; i < n; i++)
{
if (leftToRight == 0)
leftToRight = 1;
if (rightToLeft == 0)
rightToLeft = 1;
//calculate product from index 0 to n-1
leftToRight *= arr[i];
//calculate product from index n-1 to 0
rightToLeft *= arr[(n - 1) - i];
ans = max(max(leftToRight, rightToLeft), ans);
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, -2, -3, 0, 7, -8, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum Sub array product is "
<< maxSubarrayProduct(arr, n);
return 0;
}
// Java program to find Maximum Product Subarray
import java.util.*;
public class Main {
/* Returns the product of max product subarray. */
public static long maxSubarrayProduct(int[] arr, int n)
{
long ans = Integer.MIN_VALUE;
//leftToRight to store product from left to Right
long leftToRight = 1;
//rightToLeft to store product from right to left
long rightToLeft = 1;
for( int i = 0; i < n; i++ )
{
if( leftToRight == 0 ) leftToRight = 1;
if( rightToLeft == 0 ) rightToLeft = 1;
//calculate product from index 0 to n-1
leftToRight *= arr[i];
//calculate product from index n-1 to 0
rightToLeft *= arr[ (n - 1) - i ];
ans = Math.max( Math.max( leftToRight , rightToLeft ) , ans );
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
int n = arr.length;
System.out.println("Maximum Subarray product is "
+ maxSubarrayProduct(arr, n));
}
}
# Python program to find Maximum Product Subarray
import sys
# Returns the product of max product subarray.
def maxSubarrayProduct(arr, n):
ans = -sys.maxsize - 1 # Initialize the answer to the minimum possible value
leftToRight = 1 #leftToRight to store product from left to Right
rightToLeft = 1 #leftToRight to store product from right to left
for i in range(n):
if( leftToRight == 0 ):
leftToRight = 1
if( rightToLeft == 0 ):
rightToLeft = 1
leftToRight *= arr[i] #calculate product from index 0 to n-1
rightToLeft *= arr[ ( n - 1 ) - i ] #calculate product from index n-1 to 0
ans = max( max(leftToRight,rightToLeft),ans )
return ans
# Driver code
arr = [1, -2, -3, 0, 7, -8, -2]
n = len(arr)
print("Maximum Subarray product is", maxSubarrayProduct(arr, n))
using System;
public class MainClass {
// Returns the product of max product subarray.
public static int MaxSubarrayProduct(int[] arr, int n)
{
int ans = int.MinValue; // Initialize the answer to the minimum possible value
// leftToRight to store product from left to Right
int leftToRight = 1;
// rightToLeft to store product from right to left
int rightToLeft = 1;
for (int i = 0; i < n; i++)
{
if (leftToRight == 0)
leftToRight = 1;
if (rightToLeft == 0)
rightToLeft = 1;
//calculate product from index 0 to n-1
leftToRight *= arr[i];
//calculate product from index n-1 to 0
rightToLeft *= arr[(n - 1) - i];
ans = Math.Max(Math.Max(leftToRight, rightToLeft), ans);
}
return ans;
}
// Driver code
public static void Main()
{
int[] arr = { 1, -2, -3, 0, 7, -8, -2 };
int n = arr.Length;
Console.WriteLine("Maximum Subarray product is "
+ MaxSubarrayProduct(arr, n));
}
}
// JavaScript program to find Maximum Product Subarray
// Function to find the maximum product subarray
function maxSubarrayProduct(arr, n) {
let ans = -Infinity;
//leftToRight to store product from left to Right
let leftToRight = 1;
//rightToLeft to store product from right to left
let rightToLeft = 1;
for( let i = 0; i < n; i++ )
{
if( leftToRight == 0 ) leftToRight = 1;
if( rightToLeft == 0 ) rightToLeft = 1;
//calculate product from index 0 to n-1
leftToRight *= arr[i];
//calculate product from index n-1 to 0
rightToLeft *= arr[ (n - 1) - i ];
ans = Math.max( Math.max( leftToRight , rightToLeft ) , ans );
}
return ans;
}
// Driver code
const arr = [1, -2, -3, 0, 7, -8, -2];
const n = arr.length;
console.log(`Maximum Subarray product is ${maxSubarrayProduct(arr, n)}`);
//This code is written by Sundaram
Output
Maximum Sub array product is 112
Time Complexity: O(N)
Auxiliary Space: O(1)
Maximum Product Subarray
Given an array that contains both positive and negative integers, the task is to find the product of the maximum product subarray.
Examples:
Input: arr[] = {6, -3, -10, 0, 2}
Output: 180
Explanation: The subarray is {6, -3, -10}Input: arr[] = {-1, -3, -10, 0, 60}
Output: 60
Explanation: The subarray is {60}
Contact Us