美文网首页
两道类似题LeetCode152 和LeetCode714

两道类似题LeetCode152 和LeetCode714

作者: 恰似一碗咸鱼粥 | 来源:发表于2018-12-16 19:59 被阅读0次

    152


    int maxProduct(vector<int>& nums) {
        if(nums.size()==1)
            return nums[0];
        vector<vector<int>> dp(nums.size(),vector<int> (2));
        if(nums[0]<=0)
            dp[0][0]=nums[0];
        else
            dp[0][1]=nums[0];
        for(int i=1;i<nums.size();++i)
        {
                dp[i][1]=max(dp[i-1][1]*nums[i],dp[i-1][0]*nums[i])>nums[i]?max(dp[i-1][1]*nums[i],dp[i-1][0]*nums[i]):nums[i];
                dp[i][0]=min(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i])<nums[i]?min(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i]):nums[i];
        }
        int max=-100;
        for(int k=0;k<nums.size();++k)
        {
            if(dp[k][1]>max)
                max=dp[k][1];
        }
        return max;
    }
    

    714


    int maxProfit(vector<int>& prices, int fee) {
        int cash=0;
        int buy=-prices[0];
        for(int i=1;i<prices.size();++i)
        {
            cash=cash>prices[i]+buy-fee?cash:prices[i]+buy-fee;
    
            buy=buy>cash-prices[i]?buy:cash-prices[i];
        }
        return cash;
    }
    

    相关文章

      网友评论

          本文标题:两道类似题LeetCode152 和LeetCode714

          本文链接:https://www.haomeiwen.com/subject/pxwxkqtx.html