Maximum product subarray in a given array in C

Maximum product of sub-array IN C

Find the maximum product subarray in a given array in C

In this article, we will brief in on how to find the maximum product subarray of a given array .We will perform task to find the subarray from the given input array whose product is maximum . It will help us find the contiguous sub-array with atleast one element which has the largest product.

Algorithm

  1. Enter the elements.
  2. If array[0] > 0
  3. maximum = array[k]
  4. Initialize maximum_so_far = array[k].
  5. Repeat from k = 1 till the end .
  6. Multiply maximum with the next array element if it is positive
  7. Update maximum = max_so_far.
  8. Else,skip the array element 
  9. Move to the next array element.
  10. Return max_so_far.

C Code Based on above algorithm

#include<stdio.h>
int minimum (int m, int n)
{
return m < n ? m : n;
}

int maximum (int m, int n)
{
return m > n ? m : n;
}

int maxSubarrayProduct (int arr[], int a)
{
int max_ending_here = 1;
int min_ending_here = 1;
int MAXIMUM = 1;
for (int i = 0; i < a; i++)
{
if (arr[i] > 0)
{
max_ending_here = max_ending_here * arr[i];
min_ending_here = minimum (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 = maximum (min_ending_here * arr[i], 1);
min_ending_here = temp * arr[i];
}
if (MAXIMUM < max_ending_here)
MAXIMUM = max_ending_here;
}
return MAXIMUM;
}
int main ()
{
int length;
printf ("Enter the size: ");
scanf ("%d", &length);
int array[10];
printf ("Enter the elements : ");
for (int i = 0; i < length; i++)
scanf ("%d", &array[i]);\
printf ("Maximum product : %d", maxSubarrayProduct (array, length));
return 0;

}
Input:

Enter the size: 6
Enter the elements : 9 6 3 4 8 2

Output:
Maximum product : 10368