Leetcode第123、188题 买卖股票的最佳时机 C++解法

都是用动态规划去做;
123题

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size=prices.size();
        int buy1=-prices[0],sell1=0,buy2=-prices[0],sell2=0;
        for(int i=1;i<size;++i)
        {
            sell2=max(sell2,buy2+prices[i]);
            buy2=max(buy2,sell1-prices[i]);
            sell1=max(sell1,buy1+prices[i]);
            buy1=max(buy1,-prices[i]);
        }
        return sell2;
    }
};

188题

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size()<2)
            return 0;
        vector<int> dp(2*k+1,0);
        for(int i=1;i<=k;++i)
            dp[2*i-1]=-prices[0];
        for(int p:prices)
            for(int i=1;i<=2*k;++i)
                // {if(i%2)
                //     dp[i]=max(dp[i],dp[i-1]-p);
                // else
                //     dp[i]=max(dp[i],dp[i-1]+p);
                dp[i]=max(dp[i],(1-i%2*2)*p+dp[i-1]);
        return dp[2*k];
    }
};
上一篇:我掏空了各大搜索引擎,给你整理了188道Java面试题,满满干货记得收藏


下一篇:2021年将新推188部动画,爱优腾加上B站你选谁?