Program to find maximum product subarray in C

 

Program to find maximum product subarray in C

To find maximum product subarray two method or solution are possible first is brute force method that complexity is O(n^3).

In brute force method find all subarray then find maximum sum subarray.

For example

If array is 

    int a[5]={-1,2,3,4,-6};

Then subarray from this array is 

=n*(n+1)/2

=5(5+1)/2=15

So maximum subarray is 15.

{-1}      so product=-1

{-1,2}.         Product=-2

{-1,2,3}.       Product=-6

{-1,2,3,4}.      Product=-24

{-1,2,3,4,-6}.   Product=144

{2}.                Product=2

{2,3}.             Product=6

{2,3,4}.         Product=24

{2,3,4,-6}.      Product=-144

{3}.                 Product=3

{3,4}              product=12

{3,4,-6}.          Product=-72

{4}.                Product=4

{4,-6}.             Product=-24

{-6}.               Product=-6

So maximum product subarray is =144

Method 1: brust force

#include <stdio.h>

void main() {

    int a[5]={-1,2,3,4,-6};

    int n=5;

    int i,j,k;

    int product;

    int max=0;

    for(i=0;i<n;i++)

    {

        for(j=i;j<n;j++)

        {

            product=1;

            for(k=i;k<j;k++)

            {

                product*=a[k];

                if(product>max)

                {

                    max=product;

                }

            }

        }

    }

    printf("%d",max);

}

But the complexity to find maximum product subarray is O(n^3) because three for loop is used in the program.

Method 2: optimal solution to find maximum product subarray.

#include <stdio.h>

void main() {

   int a[5]={-1,2,3,4,-6};

   int n=5;

   int i;

   int pre=1;

   int suff=1;

   int ans=0;

   for(i=0;i<n;i++)

   {

       if(pre==0)

       pre=1;

       if(suff==0)

       suff=1;

       pre=pre*a[i];

       suff=suff*a[n-i-1];

       if(pre>=suff&&pre>ans)

       ans=pre;

       if(suff>pre&&suff>ans)

       ans=suff;

   }

   printf("%d",ans);

}

In optimal solution to find product of subarray

Complexity is O(n) which is less than brust force method.