Maximum Product SubArray

Maximum Product SubArray

  January 31, 2018    

---

Idea is to use concept of window sliding.
We will multiply array elements until it is 0 and whenever we detect a 0 then we will divide max by start position and look for next maximum value.


Code:

static long max=1,temp=1;
  public static void getMax(int arr[],int start,int n)
  {
  int j=start;
  while(j<n)
  {
      if(arr[j]!=0){
  temp/=arr[j];
  max=Math.max(temp,max);}
  ++j;
  }
  }
public static void maxProductSubArray(int arr[],int n)
{
int start=0;
for(int i=0;i<n;++i)
{
if(arr[i]==0 && temp!=-1)
{
getMax(arr,start,i);
start=i;
}
else if(arr[i]!=0)
{
temp*=arr[i];
max=Math.max(max,temp);
}
}
getMax(arr,start,n);
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
max=1;temp=1;
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    maxProductSubArray(arr,n);
    System.out.println(max);
}
}


Another Approach (Source GeeksforGeeks)

Here we are keeping two values min and max so far , we will find max value by multiplying with positive value to itself and negative value to min value.

static int maxSubarrayProduct(int arr[])
{
int n = arr.length;
// max positive product ending at the current position
int max_ending_here = 1;

// min negative product ending at the current position
int min_ending_here = 1;

// Initialize overall max product
int max_so_far = 1;

/* Traverse through the array. Following
values are maintained after the ith iteration:
max_ending_here is always 1 or some positive product
ending with arr[i]
min_ending_here is always 1 or some negative product
ending with arr[i] */
for (int i = 0; i < n; i++)
{
/* If this element is positive, update max_ending_here.
Update min_ending_here only if min_ending_here is
negative */
if (arr[i] > 0)
{
max_ending_here = max_ending_here*arr[i];
min_ending_here = min (min_ending_here * arr[i], 1);
}

/* If this element is 0, then the maximum product cannot
end here, make both max_ending_here and min_ending
_here 0
Assumption: Output is alway greater than or equal to 1. */
else if (arr[i] == 0)
{
max_ending_here = 1;
min_ending_here = 1;
}

/* If element is negative. This is tricky
max_ending_here can either be 1 or positive.
min_ending_here can either be 1 or negative.
next min_ending_here will always be prev.
max_ending_here * arr[i]
next max_ending_here will be 1 if prev
min_ending_here is 1, otherwise
next max_ending_here will be
prev min_ending_here * arr[i] */
else
{
int temp = max_ending_here;
max_ending_here = max (min_ending_here * arr[i], 1);
min_ending_here = temp * arr[i];
}

// update max_so_far, if needed
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}

return max_so_far;
}