艾恩凝
个人博客 https://aeneag.xyz/
今天第二题,都是动态规划
题目链接
https://leetcode-cn.com/problems/maximum-product-subarray/
分析
/*
* [2 3 -2 4]
* 动态规划
* f[i] g[i] 表示以当前节点结尾的连续子数组的max,min值
* 首先我们不知道最大值是否是正数还是负数
* 1) 计算最大值
* 当nums[i] >= 0 时
* 1.把当前节点的值看作子数组,
* 2.当前节点与前一个最大连续子数组(f[i-1])相乘,组成该节点的子数组
* 当nums[i] < 0 时
* 1.把当前节点的值看作子数组,
* 2.当前节点与前一个最小连续子数组(g[i-1])相乘,组成该节点的子数组
* 最后比较最大值
* nums[i] nums[i]*f[i-1] nums[i]*g[i-1]
* 2) 计算最小值
* 当nums[i] >= 0 时
* 1.把当前节点的值看作子数组,
* 2.当前节点与前一个最小连续子数组(g[i-1])相乘,组成该节点的子数组
* 当nums[i] < 0 时
* 1.把当前节点的值看作子数组,
* 2.当前节点与前一个最小连续子数组(f[i-1])相乘,组成该节点的子数组
* 最后比较最大值
* nums[i] nums[i]*f[i-1] nums[i]*g[i-1]
*/
题解
未优化
class Solution {
public:
int maxProduct(vector<int>& nums) {
int len = nums.size(),res = nums[0];
vector<int> f(len+1,0),g(len+1,0);
f[0] = nums[0],g[0] = nums[0];
for(int i = 1 ; i < len ; ++i){
f[i] = max(nums[i], max(f[i - 1] * nums[i], g[i - 1] * nums[i]));
g[i] = min(nums[i], min(g[i - 1] * nums[i], f[i - 1] * nums[i]));
res = max(res,f[i]);
}
return res;
}
};
优化
class Solution {
public:
int maxProduct(vector<int>& nums) {
int len = nums.size(),res = nums[0];
int max_num= nums[0] , min_num = nums[0],max_tmp = nums[0],min_tmp = nums[0];
for(int i = 1 ; i < len ; ++i){
max_tmp = max_num,min_tmp = min_num;
max_num = max(nums[i], max(max_tmp * nums[i], min_tmp * nums[i]));
min_num = min(nums[i], min(max_tmp * nums[i], min_tmp * nums[i]));
res = max(res,max_num);
}
return res;
}
};
欢迎关注 #公众号:技术乱舞 一起交流学习进步