Program to find the maximum product subarray in a given array | Faceprep

Program to find the maximum product subarray in a given array is discussed here. Given an array of integers as input, the task is to find the subarray from the given input array whose product is maximum.

For example, consider the given array

Input: {-1, -3, -10, 60,0} 
Output: 1800
Sub-array : {-3, -10, 60}
Product of the sub-array = -3 * -10 * 60 = 1800

Algorithm to find the maximum product subarray in the given array

  1. Input the array elements.
  2. If arr[0] > 0, max = arr[i] and initialize max_so_far = arr[i].
  3. Repeat from i = 1 to end of the array.
  4. Multiply max with the next array element if it is positive and update max = max_so_far.
  5. Else, skip the array element and move to the next array element.
  6. Return max_so_far.

Program to find the maximum product subarray in the given array is given below.

// C program to find the maximum product subarray in the given array

#include
#include

int min (int x, int y) {return x < y? x : y; }
int max (int x, int y) {return x > y? x : y; }

int maxSubarrayProduct(int arr[], int n)
{
int max_ending_here = 1;
int min_ending_here = 1;
int max_so_far = 1;
for (int i = 0; i < n; i++)
{
if (arr[i] > 0)
{
max_ending_here = max_ending_here*arr[i];
min_ending_here = min (min_ending_here * arr[i], 1);
}
else if (arr[i] == 0)
{
max_ending_here = 1;  // max at current position
min_ending_here = 1;
}
else
{
int temp = max_ending_here;  // temp variable to store max
max_ending_here = max (min_ending_here * arr[i], 1);  // update maximum product
min_ending_here = temp * arr[i];
}
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;  // update max value
}
return max_so_far;   // return the max value
}
int main()
{
int siz;
printf(“\nEnter the size of the array : “);
scanf(“%d”,&siz);
int arr[10];

// Input the array elements
printf(“\nInput the array elements : “);
for(int i=0;i<siz;i++)
scanf(“%d”,&arr[i]);
printf(“\nMaximum product : %d\n”,maxSubarrayProduct(arr, siz)); // call the function
return 0;
}

// C++ program to find the maximum product subarray in the given array

#include
using namespace std;

int min (int x, int y) {return x < y? x : y; }  // find the minimum element
int max (int x, int y) {return x > y? x : y; }  // find the maximum element

// Function to find the maximum product subarray

int maxSubarrayProduct(int arr[], int n)
{
int max_ending_here = 1;  // Initialize values
int min_ending_here = 1;
int max_so_far = 1;
for (int i = 0; i < n; i++)
{
if (arr[i] > 0)
{
max_ending_here = max_ending_here*arr[i]; // update max value
min_ending_here = min (min_ending_here * arr[i], 1);
}
else if (arr[i] == 0)
{
max_ending_here = 1;
min_ending_here = 1;
}
else
{
int temp = max_ending_here;  // temp variable to store max value
max_ending_here = max (min_ending_here * arr[i], 1);
min_ending_here = temp * arr[i];
}
if (max_so_far < max_ending_here)
max_so_far = max_ending_here; // update max value
}
return max_so_far;  // return maximum product
}


int main()
{
int siz;
cout << “\nEnter the size of the array : “;
cin>>siz;
int arr[10];
cout << “\nInput the array elements : “;
for(int i=0;i<siz;i++)
cin>>arr[i];
cout << “\nMaximum product : “;
cout<<maxSubarrayProduct(arr, siz) << endl;
return 0;
}

// Java program to find the maximum product subarray in the given array

public class Main
{
static int min (int x, int y) {return x < y? x : y; }
static int max (int x, int y) {return x > y? x : y; }

static int maxSubarrayProduct(int arr[], int n)
{
int max_ending_here = 1;
int min_ending_here = 1;
int max_so_far = 1;
for (int i = 0; i < n; i++)
{
if (arr[i] > 0)
{
max_ending_here = max_ending_here*arr[i];
min_ending_here = min (min_ending_here * arr[i], 1);
}
else if (arr[i] == 0)
{
max_ending_here = 1;
min_ending_here = 1;
}
else
{
int temp = max_ending_here;
max_ending_here = max (min_ending_here * arr[i], 1);
min_ending_here = temp * arr[i];
}
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
public static void main(String[] args)
{
int[] arr = new int[]{-1, -3, -10, 60,0};
int siz = arr.length;
System.out.print(“\nMaximum product subarray : “);
System.out.print(maxSubarrayProduct(arr, siz));
}
}

# Python program to find the maximum product subarray in the given array

# Function to find the product of max product subarray.
def maxsubarrayproduct(arr):

n = len(arr)

# max positive product ending at the current position
max_ending_here = 1

# min positive product ending at the current position
min_ending_here = 1

# Initialize max so far
max_so_far = 1

for i in range(0,n):
if arr[i] > 0:
max_ending_here = max_ending_here*arr[i]
min_ending_here = min (min_ending_here * arr[i], 1)

elif arr[i] == 0:
max_ending_here = 1
min_ending_here = 1

else:
temp = max_ending_here
max_ending_here = max (min_ending_here * arr[i], 1)
min_ending_here = temp * arr[i]
if (max_so_far < max_ending_here):
max_so_far = max_ending_here
return max_so_far

arr = [1, -3, -10, 60, 0]
print (“Maximum product subarray :”,maxsubarrayproduct(arr) )

 

Output:

maximum product subarray in the given array

Time complexity: O(n)