第一題乘積max子數組[1h++]

emmmm感覺看不懂題解

線性dp【計劃學一下acwing，挨個做一下】

線性動態規劃 相似題解析 最長上升子序列 最大上升子序列和 最大連續子段和 乘積最大子數組_嗶哩嗶哩_bilibili

比較奇怪的就是有正負數和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;}
};