乘积最大子序列 -dp
2020-06-02 本文已影响0人
fdsun
找出一个序列中乘积最大的连续子序列(至少包含一个数)。
样例
样例 1:
输入:[2,3,-2,4]
输出:6
样例 2:
输入:[-1,2,4,1]
输出:8
注意事项
数组长度不超过20000
乘积最大的子序列的积,小于2147483647
/**
* a[j]
* a[j-1]*a[j]
* if a[j]>0 a[j-1] most max
* if a[j]<0 a[j-1] most min
* <p>
* f[j] most max
* g[j] most min
* <p>
* f[j] = max{ a[j], max{ a[j]*f[j-1]],a[j]]*f[j-1] } }
* g[j] = min{ a[j], min{ a[j]*f[j-1]],a[j]]*f[j-1] } }
*
* @param nums: An array of integers
* @return: An integer
*/
public static int maxProduct(int[] nums) {
// write your code here
int n = nums.length;
if (n == 0) {
return 0;
}
int[] f = new int[n];
int[] g = new int[n];
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (i == 0) {
f[i] = nums[i];
g[i] = nums[i];
} else {
f[i] = Math.max(nums[i], Math.max(nums[i] * f[i - 1], nums[i] * g[i - 1]));
g[i] = Math.min(nums[i], Math.min(nums[i] * f[i - 1], nums[i] * g[i - 1]));
}
res = Math.max(res, f[i]);
}
return res;
}