题目
链接
题解
class Solution {
/**
* 设 fmax[n] 为以 nums[n] 结尾子数组的最大乘积
* 设 fmin[n] 为以 nums[n] 结尾子数组的最小乘积
* 转移方程：
* fmax[n] = max(fmax[n - 1] * nums[n], fmin[n - 1] * nums[n], nums[n])
* fmin[n] = min(fmax[n - 1] * nums[n], fmin[n - 1] * nums[n], nums[n])
*/
// public int maxProduct(int[] nums) {
// int len = nums.length;
// int[] maxDp = new int[len];
// int[] minDp = new int[len];
// System.arraycopy(nums, 0, maxDp, 0, len);
// System.arraycopy(nums, 0, minDp, 0, len);
// for (int i = 1; i < len; i++) {
// int max = Math.max(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]);
// int min = Math.min(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]);
// maxDp[i] = Math.max(max, nums[i]);
// minDp[i] = Math.min(min, nums[i]);
// }
// int res = maxDp[0];
// for (int i = 1; i < len; i++) {
// if (maxDp[i] > res) {
// res = maxDp[i];
// }
// }
// return res;
// }
/**
* 优化版
*/
public int maxProduct(int[] nums) {
int len = nums.length;
int maxDp = nums[0], minDp = nums[0], res = nums[0];
for (int i = 1; i < len; i++) {
int max = Math.max(maxDp * nums[i], minDp * nums[i]);
int min = Math.min(maxDp * nums[i], minDp * nums[i]);
maxDp = Math.max(max, nums[i]);
minDp = Math.min(min, nums[i]);
// 记录答案
res = Math.max(res, maxDp);
}
return res;
}
}