刷leetcode-hot100-动态规划3.12-
目录
刷leetcode hot100–动态规划3.12
第一题乘积max子数组[1h++]
emmmm感觉看不懂题解
线性dp【计划学一下acwing，挨个做一下】
比较奇怪的就是有正负数和0，如何处理？
核心是维护一个max和min
//全是整数【负数，0，正数】，乘积max,连续子数组
//暴力求解？？起始i,终止j，遍历
//dp[n]以nums[n]结束的连续子数组的max乘积
//初始化dp[n] = nums[n]
//有负数怎么办？？，或者说其实是整数的话，只用关注0，负数
//负数和0如何处理
//负数和0分开处理，负数看奇数偶数，0分左右两边/就是0
//看了评论区，两个能合起来：负数偶数【不用管，遍历取max】，
//首先不用管0,因为int a = 1,int max = nums[0],如果遇到0，a = 1即可
//负数：负数奇数【若无0，则为左边数组，右边数组取max】,有0，分成两半，看左边负数个数，右边负数个数，依旧是无0的操作
//一个很厉害的方法是从左向右和从右向左遍历一次，负数？？取max
//dp想法是维护min和max
题解：
class Solution {
public:
int maxProduct(vector<int>& nums) {
long maxF = nums[0], minF = nums[0], ans = nums[0];
for (int i = 1; i < nums.size(); ++i) {
long mx = maxF, mn = minF;
maxF = max(mx * nums[i], max((long)nums[i], mn * nums[i]));
minF = min(mn * nums[i], min((long)nums[i], mx * nums[i]));
if(minF<INT_MIN) {
minF=nums[i];
}
ans = max(maxF, ans);
}
return ans;
}
};