10/02/2014

Leetcode -- Maximum Product Subarray

Made a really complicated and ugly solution, will refactor later:

public class Solution {
    public int maxProduct(int[] A) {
         List B = new ArrayList();
        for(int i = A.length - 1; i >= 0; --i) {
            B.add(A[i]);
        }

        int[] BB = new int[A.length];
        for(int i = 0; i < A.length; ++i) {
            BB[i] = B.get(i);
        }
        return Math.max(maxProductHelper(A), maxProductHelper(BB));
    }
    public int maxProductHelper(int[] A) {
  int currentMax = A[0];
        int product = A[0];
        int grandproduct = A[0];

        for(int i = 1; i < A.length; ++i) {
            grandproduct *= A[i];

            if(A[i] == 0) {
                currentMax = Math.max(currentMax, 0);
                currentMax = Math.max(currentMax, product);
                product = 0;
                grandproduct = 1;
            } else if(A[i] < 0) {
                  currentMax = Math.max(currentMax, product);
                if(grandproduct > 0) {
                    product = grandproduct;
                    currentMax = Math.max(currentMax, product);
                }
                else if (grandproduct == 0) {
                    grandproduct = A[i];
                        product = A[i];
                } else {
                    product = 0;
                }
            } else {
                  if(grandproduct == 0) {
                    grandproduct = A[i];
                }
                if(product == 0) {
                    product = 1;
                }
                product *= A[i];
                currentMax = Math.max(currentMax, product);
            }
        }
        return currentMax;
    }
}

No comments: