Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
mlgb的，今天遇到这个题搞了半天。记录下。
首先解放可以使用穷举。通过二维数组product[i][j]记录从i到j的乘积，然后遍历得到数组中最大元素，就是答案。
public int maxProduct(int[] A) {
int[][] product = new int[A.length][A.length];
int max = A[0];
for(int i = 0; i < A.length; i++) {
product[i][i] = A[i];
for (int j = i + 1; j < A.length; j++) {
product[i][j] = product[i][j - 1] * A[j];
max = Math.max(max, product[i][j]);
}
max = Math.max(max, A[i]);
}
return max;
}
简单明了。但是当然是超时。
然后撸主想了很久，期间还看了部电影。
假设第i元素是个正数，那么我们要计算当前i个元素的最大乘积p[i]，就要 知道前面i-1的最大乘积p[i-1]，p[i] = p[i - 1] * A[i];
假设第i元素是个负数，那么我们要计算当前i个元素的最大乘积p[i]，就要知道前面i-1的最小乘积（负数）n[i-1], p[i] = n[i - 1] * A[i];
p[i]表示以第i元素结尾，能取到的最大乘积；n[i]表示以第i元素结尾，能取到的负乘积。如果i元素是0的花，一切归0，p[i] = n[i] = 0.
public int maxProduct2(int[] A) {
if (A.length == 1) {
return A[0];
}
int[] p = new int[A.length];
int[] n = new int[A.length];
int max = Integer.MIN_VALUE;
for (int i = 0; i < A.length; i++) {
if (A[i] > 0) {
p[i] = (i > 0 && p[i - 1] > 0) ? p[i - 1] * A[i] : A[i];
n[i] = (i > 0 && n[i - 1] < 0) ? n[i - 1] * A[i] : 0;
} else if (A[i] < 0) {
p[i] = (i > 0 && n[i - 1] < 0) ? n[i - 1] * A[i] : 0;
n[i] = (i > 0 && p[i - 1] > 0) ? p[i - 1] * A[i] : A[i];
} else {
max = Math.max(max, 0);
}
if (p[i] > 0) {
max = Math.max(max, p[i]);
} else if (n[i] < 0) {
max = Math.max(max, n[i]);
}
}
return max;
}
因为遇到0的时候，其实是新的起点。
上面的代码可以简化为使用常量空间的下面的可读性较差的代码。
public int maxProduct(int[] A) {
if (A.length == 1) {
return A[0];
}
int p = 0;
int n = 0;
int max = Integer.MIN_VALUE;
for (int i = 0; i < A.length; i++) {
int np = p > 0 ? p * A[i] : A[i];
int nn = n < 0 ? n * A[i] : 0;
if (A[i] > 0) {
p = np;
n = nn;
} else if (A[i] < 0) {
p = nn;
n = np;
} else {
p = 0;
n = 0;
max = Math.max(max, 0);
continue;
}
if (p > 0) {
max = Math.max(p, max);
} else if (n < 0) {
max = Math.max(n, max);
}
}
return max;
}