Maximum Product Subarray

MaximumProductSubarray.java

//Most Simple

public class Solution {
    public int maxProduct(int[] A) {
      
        if (A == null || A.length == 0) {
            return 0;
        }
        int max = A[0], min = A[0], result = A[0];
        for (int i = 1; i < A.length; i++) {
            int temp = max;
            max = Math.max(Math.max(max * A[i], min * A[i]), A[i]);
            min = Math.min(Math.min(temp * A[i], min * A[i]), A[i]);
            if (max > result) {
                result = max;
            }
        }
        return result;
    }
}

//with printing

import java.lang.Math; 

public class Solution {
  
  public static void main(String[] args){
    
    int[] arr = {2,3,-2,4, -2, -5};
    int max = maxProduct(arr);
    
    System.out.println(String.format("Max Product: %-4d", max));
    
  }
  
  
  public static int maxProduct(int[] A) {
      
        if (A == null || A.length == 0) {
            return 0;
        }
        int max = A[0], min = A[0], result = A[0];
        for (int i = 1; i < A.length; i++) {
            int temp = max;
            max = Math.max(Math.max(max * A[i], min * A[i]), A[i]);
            min = Math.min(Math.min(temp * A[i], min * A[i]), A[i]);
            System.out.println(String.format("Max: %-4d, Min: %-4d", max, min));
            if (max > result) {
                result = max;
            }
        }
        return result;
    }
}

/*output
Max: 6   , Min: 3   
Max: -2  , Min: -12 
Max: 4   , Min: -48 
Max: 96  , Min: -8  
Max: 40  , Min: -480
Max Product: 96  


*/


//Alternate

public class Solution {
    public int maxProduct(int[] A) {
       int n = A.length;
       if (n==0) return 0;
 
        int maxi = 1, mini = 1;
        int out = Integer.MIN_VALUE;
 
        for (int i=0;i<n;i++) {
            int oldmaxi = Math.max(maxi,1);
            if (A[i] > 0) {
                maxi = oldmaxi*A[i];
                mini *= A[i];
            } else {
                maxi = mini*A[i];
                mini = oldmaxi*A[i];
            }
            out = Math.max(out,maxi);
        }
 
        return out;
    }
}

//With printing for debugging:

public class Solution {
  
  public static void main(String[] args){
    
    int[] arr = {2,3,-2,4, -2, -5};
    int max = maxProduct(arr);
    
    System.out.println(String.format("Max Product: %-4d", max));
    
  }
  
  
  public static int maxProduct(int[] A) {
    int n = A.length;
    if (n==0) return 0;

    int maxi = 1, mini = 1;
    int out = Integer.MIN_VALUE;

    for (int i=0;i<n;i++) {
      int oldmaxi = Math.max(maxi,1);
      System.out.println(String.format("oldmaxi: %-4d", oldmaxi));
      if (A[i] > 0) {
        maxi = oldmaxi*A[i];
        mini *= A[i];
        System.out.println(String.format("A[i] > 0 Maxi: %-4d, Mini: %-4d", maxi, mini));
      } else {
        maxi = mini*A[i];
        mini = oldmaxi*A[i];
        System.out.println(String.format("Else Maxi: %-4d, Mini: %-4d", maxi, mini));
      }
      out = Math.max(out,maxi);
    }

    return out;
  }
}

/*output:

oldmaxi: 1   
A[i] > 0 Maxi: 2   , Mini: 2   
oldmaxi: 2   
A[i] > 0 Maxi: 6   , Mini: 6   
oldmaxi: 6   
Else Maxi: -12 , Mini: -12 
oldmaxi: 1   
A[i] > 0 Maxi: 4   , Mini: -48 
oldmaxi: 4   
Else Maxi: 96  , Mini: -8  
oldmaxi: 96  
Else Maxi: 40  , Mini: -480
Max Product: 96  


*/