Recent Posts

Maximum Product Sub-array Problem

Written by

studymite

Input: [2,3,-2,4]
Output: 6

The Maximum Product Sub-Array problem asks the user to find the subarray with the largest possible product. Sounds, Easy right?

The catch is to calculate the highest product keeping in mind that the array size can vary, as well as the fact that the locations have to be contiguous. This is explained simply below:

Again, we employ two approaches to solve this problem:

1. Brute Force
2. Divide and Conquer
There also exists a third way, which is known as Kadane’s Algorithm, but we won’t go into that in this section.

# Approach 1: Brute force
In Brute force, the pseudo-code is to:

  1. Find all the possible subarrays
  2. Find the maximum.

 

Code:


void MaxProductSubArray( int * a, int size)
{ int MaxProduct = a[0];
  int MaxProductStart = 0, MaxProductEnd = 0;

for( int i = 1; i < size; i++) { int tempProduct = 0; int j = i; while(j>=0)
{ tempProduct *= a[j];
if ( tempProduct > MaxProduct )
{ MaxProduct = tempProduct;
MaxProductStart = j;
MaxProductEnd = i;
}
j--;
}  );
cout << "Max Product in the array : " << MaxProduct << endl;
cout << "Max Product Start : " << MaxProductStart << " MaxProductEnd : " << MaxProductEnd << endl;
}

 

# APPROACH 2: Optimized Approach
Here, the idea is to traverse array from left to right keeping two variables minEnd and maxEnd which represents the minimum and maximum product value till the ith index of the array. Now, if the ith element of the array is negative that means now the values of minEnd and maxEnd will be swapped as value of maxEnd will become minimum by multiplying it with a negative number. Now, compare the minEnd and maxEnd.

The value of minEnd and maxEnd depends on the current index element or the product of the current index element and the previous minEnd and maxEnd respectively

Code:


#include <bits/stdc++.h> 
using namespace std; 

int maxSubarray(int givenArray[], int n)
{
int minEnd = 1;


int minEnd = 1; 

int maxSoFar = 1; 
int flag = 0; 
for (int i = 0; i &lt; n; i++) { if (givenArray[i] &gt; 0) { 
        minEnd = minEnd * givenArray[i]; 
        minEnd = min(minEnd * givenArray[i], 1); 
        flag = 1; 
    } 

    else if (givenArray[i] == 0) { 
        minEnd = 1; 
        minEnd = 1; 
    } 
      else { 
        int temp = minEnd; 
        minEnd = max(minEnd * givenArray[i], 1); 
        minEnd = temp * givenArray[i]; 
    } 

    if (maxSoFar &lt; minEnd) 
        maxSoFar = minEnd; 
} 
if (flag == 0 &amp;&amp; maxSoFar == 1) 
    return 0; 
return maxSoFar; 



}


int main()
{
int givenArray[] = { 12, 4234, 34234, -21,-231,-1};
int n = sizeof(givenArray) / sizeof(givenArray[0]);
cout << "Maximum Sub givenArray product is "
<< maxSubarray(givenArray, n);
return 0;
}

This is how the Maximum product Subarray problem is solved.

Maximum Product Sub-array Problem