[leetcode]动态规划之Maximum Product Subarray

女爷i 2021-09-28 14:52 329阅读 0赞

### 动态规划之Maximum Product Subarray ###

*  题目
 *  思考
 *  类型归类
 *  代码

# 题目 #

[leetcode入口][leetcode]

# 思考 #

特殊在于，数组元素可能是0或者是负数。  
当遇到负数的时候，最大值和最小值间会出现翻转，  
即：最大值会变成最小值，最小值会变成最大值

维护两个数组  
dpmin\[i\]：存储以元素\[i\]为结尾的连续一段的最大值  
dpmax\[i\]：存储以元素\[i\]为结尾的连续一段的最小值

每次遍历都要 res=max(res,dpmax\[i\])

# 类型归类 #

我把这种题目归类为，  
求一组数某一连续范围的最大值/最小值问题  
解法：  
通常维护的dp数组的每个元素dp\[i\]要以第i个元素作为结尾  
然后要求最大/最小，最后要遍历整个dp数组取最大/最小，或者在遍历的时候维护min和max变量

# 代码 #

class Solution { 
    public:
        int maxProduct(vector<int>& nums) { 
            int res=nums[0];
            
            vector<int> dpmin(nums.size());
            vector<int> dpmax(nums.size());
            
            dpmin[0]=dpmax[0]=nums[0];
            
            for(int i=1;i<nums.size();i++){ 
                dpmin[i]=min(min(dpmin[i-1]*nums[i],dpmax[i-1]*nums[i]),nums[i]);
                dpmax[i]=max(max(dpmin[i-1]*nums[i],dpmax[i-1]*nums[i]),nums[i]);
                
                res=max(res,dpmax[i]);
            }
            return res;
        }
    };

[leetcode]: https://leetcode.com/problems/maximum-product-subarray/

发表评论取消回复

表情：

评论列表（有 0 条评论，329人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has

淩亂°似流年/ 2022年08月21日 00:21/ 0 赞/ 177 阅读

相关 Maximum Product Subarray--LeetCode

Find the contiguous subarray within an array (containing at least one number) which has

柔情只为你懂/ 2022年08月07日 13:35/ 0 赞/ 219 阅读

相关 LeetCode 53/152 Maximum Subarray/Maximum Product Subarray---DP **

一：[Maximum Subarray][] 题目： Find the contiguous subarray within an array (containing at

╰+哭是因爲堅強的太久メ/ 2022年08月07日 12:43/ 0 赞/ 32 阅读

相关 Maximum Subarray--LeetCode

题目： Find the contiguous subarray within an array (containing at least one number) whi

ゝ一纸荒年。/ 2022年08月07日 11:57/ 0 赞/ 38 阅读

相关 Leetcode: Maximum Subarray

题目： Find the contiguous subarray within an array (containing at least one number) whic

忘是亡心i/ 2022年08月07日 09:59/ 0 赞/ 39 阅读

相关 [leetcode]152. Maximum Product Subarray -- JavaScript 代码

/ @param {number[]} nums @return {number} / var maxProduct = function(nums) {

冷不防/ 2022年07月17日 02:13/ 0 赞/ 184 阅读

相关 LeetCode152—Maximum Product Subarray

原题 [原题链接][Link 1] > Find the contiguous subarray within an array (containing at leas

快来打我*/ 2022年07月15日 05:06/ 0 赞/ 158 阅读

相关【转载】leetcode 53. Maximum Subarray(DP动态规划问题)

问题描述： Find the contiguous subarray within an array (containing at least one number) w

短命女/ 2022年05月24日 00:47/ 0 赞/ 222 阅读

相关（Java）leetcode-53 Maximum Subarray （动态规划）

题目【最大子序和】 Given an integer array nums, find the contiguous subarray (containing at

蔚落/ 2022年03月07日 07:20/ 0 赞/ 264 阅读

相关 [leetcode]动态规划之Maximum Product Subarray

动态规划之Maximum Product Subarray 题目思考类型归类代码题目 [leetcode入口][leetcode]

女爷i/ 2021年09月28日 14:52/ 0 赞/ 329 阅读