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;
}
}
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