152、乘积最大的子序列
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
链接：https://leetcode-cn.com/problems/maximum-product-subarray
题解
- 动态规划
dpMax[i]表示以第 i 个元素的结尾的子数组，乘积最大的值，也就是这个数组必须包含第 i 个元素。dpMax[i]表示以第 i 个元素的结尾的子数组，乘积最小的值，也就是这个数组必须包含第 i 个元素。- 空间复杂度优化
- 注意到更新 dp[i] 的时候，我们只用到 dp[i-1] 的信息，再之前的信息就用不到了。所以我们完全不需要一个数组，只需要一个变量去重复覆盖更新即可。
1、动态规划
public int maxProduct(int[] nums) {
int n = nums.length;
if (n == 0) {// 边界处理
return 0;
}
int[] dpMax = new int[n];
dpMax[0] = nums[0];
int[] dpMin = new int[n];
dpMin[0] = nums[0];
int max = nums[0];
for (int i = 0;i < n;i++) {
// Math.max 和 Math.min函数是很好的择优工具函数而不用if else 去写
dpMax[i] = Math.max(dpMin[i - 1]*nums[i],Math.max(dpMax[i - 1]*nums[i],nums[i]));
dpMin[i] = Math.min(dpMin[i - 1]*nums[i],Math.min(dpMax[i - 1]*nums[i],nums[i]));
max = Math.max(max,dpMax[i]);
}
return max;
}
// 空间优化
public int maxProduct(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int dpMax = nums[0];
int dpMin = nums[0];
int max = nums[0];
for (int i = 1;i < n;i++) {
int preMax = dpMax;
dpMax = Math.max(dpMin*nums[i],Math.max(dpMax*nums[i],nums[i]));
dpMin = Math.min(dpMin*nums[i],Math.min(preMax*nums[i],nums[i]));
max = Math.max(max,dpMax);
}
return max;
}
- 两趟扫描
public int maxProduct(int[] nums) {
int max=nums[0];
int res=1;
// 顺序扫最大，累乘,遇0变1
for(int num:nums){
res=res*num;
if(max<res)max=res;
if(num==0)res=1;
}
// 逆序扫最大，累乘,遇0变1
res=1;
for(int i=nums.length-1;i>=0;i--){
res=res*nums[i];
if(max<res)max=res;
if(nums[i]==0)res=1;
}
return max;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
