leetcode152乘积最大子数组-蒲公英云

leetcode152乘积最大子数组

题目:

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

解法:该题目开始想用滑动窗口去解决奈何找不全滑动条件就开始尝试使用动态规划

与之前动态规划不同的是最优子结构存在两个max 和 min 即上一步找到的最小子结构乘上这一步也可能是最大子结构

如果当前数值为负数那么让前面的数尽可能负的大反之正的大

代码如下:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        //考虑使用动态规划解决此题目 一般而言求最大最小 最多最少都可以用动态规划
        int res=nums[0];
        int max1=nums[0];
        int min1=nums[0];
        for(int i=1;i<nums.size();i++){
            int tem=max1;
            max1=max(max1*nums[i],min1*nums[i],nums[i]);
            min1=min(tem*nums[i],min1*nums[i],nums[i]);
            //cout<<max1<<" "<<min1<<endl;
            if(res<max1) res=max1;
        }
        return res;
    }
    int max(int a,int b,int c){
        a=a>b?a:b;
        a=a>c?a:c;
        return a;
    }
    int min(int a,int b,int c){
        a=a<b?a:b;
        a=a<c?a:c;
        return a;
    }
};