Maximum Product Subarray

Given an array we have to the subarray which has maximum product compared to other subarrays.

Input: arr[] = {6, -3, -10, 0, 2}
Output:   180  // The subarray is {6, -3, -10}

Input: arr[] = {-1, -3, -10, 0, 60}
Output:   60  // The subarray is {60}

Input: arr[] = {-2, -3, 0, -2, -40}
Output:   80  // The subarray is {-2, -40}

Concept behind:

   If the array consists of only positive elements(>0) then the maximum subarray product will be the product of all array elements.
   But in this problem we have to find it for array containing both positive and negative elements.

At each step we have three decisions to make:

i)  If the element is positive we can get the curr_maximum product by multiplying it with maximum positive product obtained so far.

ii) If the element is negative we can get curr_maximum by multiplying it with the minimum product obtained so far

iii) The element might be the starting position for maximum product subarray.(It is greater than curr_maximum)


Illustration:

Code:

import java.util.*;

public class Solution {
    
    public static void main(String[] args) {
        
         int[] a =  {-2, -3, 0, -2, -40};
         int n = a.length;
         int prev_min = a[0];
         int curr_min = a[0];
         int prev_max = a[0];
         int curr_max = a[0];
         int result = a[0];
        
         for(int i=1; i<n; i++){
             curr_max = Math.max(Math.max(prev_max*a[i], prev_min*a[i]),a[i]);
             curr_min = Math.min(Math.min(prev_max*a[i], prev_min*a[i]), a[i]);
             result = Math.max(curr_max,result);
             prev_max = curr_max;
             prev_min = curr_min;
         }
        
         System.out.print(result);
     
    }
}

Output:

80

References:
http://qr.ae/TUTgHo
https://www.geeksforgeeks.org/maximum-product-subarray/