题目
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
分析
定义f[i] = what is the max subarray product that ends with index i(inclusive) ?
怎么通过f[j], j < i 来计算f[i]?
假设我们已经知道f[j] (max subarray product that ends with index j)
那么f[i] 要么是f[j] * A[i], 要么是A[i]本身
根据上面这个直白的转移方程,我们写出以下代码
class Solution {
public int maxProduct(int[] A) {
int n = A.length, ans = A[0];
int[] f = new int[n];
f[0] = A[0];
for(int i = 1; i < n; i++) {
f[i] = Math.max(A[i], f[i - 1] * A[i]);
ans = Math.max(ans, f[i]);
}
return ans;
}
}
但是上面这个代码fail了以下test case
这是因为我们没有考虑到这个情况:
A[i] 的前面有一个非常大的负数product subarray,而且A[i]本身也是负数。两者相乘可以得出一个正数的,非常大的数字
Input:
[-2,3,-4]
Output:
3
Expected:
24
经过修改后,程序如下
class Solution {
public int maxProduct(int[] A) {
int n = A.length, ans = A[0];
int[] f = new int[n];
int[] g = new int[n];
f[0] = A[0];
g[0] = A[0];
for(int i = 1; i < n; i++) {
f[i] = Math.max(A[i], Math.max(f[i - 1] * A[i], g[i - 1] * A[i]));
g[i] = Math.min(A[i], Math.min(g[i - 1] * A[i], f[i - 1] * A[i]));
ans = Math.max(ans, f[i]);
}
return ans;
}
}
简化一下空间复杂度,最终代码如下
class Solution {
public int maxProduct(int[] nums) {
if(nums.length == 0) return 0;
int min = nums[0];
int max = nums[0];
int product = nums[0];
for(int i = 1; i < nums.length; i++) {
int nextMax = max * nums[i];
int nextMin = min * nums[i];
max = Math.max(nums[i], Math.max(nextMax, nextMin));
min = Math.min(nums[i], Math.min(nextMax, nextMin));
product = Math.max(product, max);
}
return product;
}
}