public class Solution { public int maxProduct(int[] A) { ListB = 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; } }
10/02/2014
Leetcode -- Maximum Product Subarray
Made a really complicated and ugly solution, will refactor later:
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment