一起学习交流~

乘积最大子数组-dp两种情况

算法 laomuji 8个月前 (02-02) 326次浏览 已收录 0个评论

目录

题目

给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

我是一步一步的推测的

class Solution {
/*
定义 以第i个元素结尾的数据,最大和最小乘积
2 3 -2 4 -6

2
以2结尾
最大乘积2
最小乘积2
dpMax[0]=nums[0]
dpMin[0]=nums[0]

2 3
以3结尾
最大乘积6
最小乘积3
dpMax[2]=max(nums[1],nums[1]*dpMax[0])
dpMin[2]=min(nums[1],nums[1]*dpMin[0])

2 3 -2
以-2结尾
最大乘积-2
最小乘积-12
dpMax[2]=max(nums[2],nums[2]*dpMax[1])
dpMin[2]=min(nums[2],min(nums[2]*dpMin[1],nums[2]*dpMax[1]))

2 3 -2 4
以4结尾
最大乘积4
最小乘积-48
dpMax[3]=max(nums[3],nums[3]*dpMax[2])
dpMin[3]=min(nums[3],min(nums[3]*dpMin[2],nums[3]*dpMax[2]))

2 3 -2 4 -6
以-6结尾
最大乘积288
最小乘积-24
dpMax[4]=max(nums[4],max(nums[4]*dpMax[3],nums[4]*dpMin[3]))

*/
public:
    int maxProduct(vector<int>& nums) {
        int size = nums.size();
        if(size==0)return 0;
        vector<int>dpMax(size);
        vector<int>dpMin(size);
        dpMax[0]=nums[0];
        dpMin[0]=nums[0];
        int maxNum = nums[0];
        for(int i=1;i<size;i++){
            dpMax[i]=max(nums[i],max(nums[i]*dpMax[i-1],nums[i]*dpMin[i-1]));
            dpMin[i]=min(nums[i],min(nums[i]*dpMin[i-1],nums[i]*dpMax[i-1]));
            if(dpMax[i]>maxNum)maxNum=dpMax[i];
        }
        return maxNum;
    }
};
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论