力扣刷题记录（21）LeetCode：121、123、188、309

目录

121.?买卖股票的最佳时机

?123.?买卖股票的最佳时机 III

188.?买卖股票的最佳时机 IV?

?309.?买卖股票的最佳时机含冷冻期

---

如果某一天出售股票可以得到最大利润，那么股票买入的价格一定是这天之前股票的最低价格。

所以我们可以在遍历股票价格的时候不断更新股票的最低价格，然后尝试在今天卖出，不断取能够卖出的最大利润。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans=0,minval=INT_MAX;
        for(int i=0;i<prices.size();i++)
        {
            //更新股票的最低价格
            minval=min(minval,prices[i]);
            //更新最大利润
            ans=max(ans,prices[i]-minval);
        }
        return ans;
    }
};

?123.?买卖股票的最佳时机 III

?

每只股票一共有五种状态：

0.未曾持过股

1.第一次持股

2.第一次卖出

3.第二次持股

4.第二次卖出

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<int> dp(5, 0);
        dp[1] = -prices[0];
        dp[3] = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp[1] = max(dp[1], dp[0] - prices[i]);
            dp[2] = max(dp[2], dp[1] + prices[i]);
            dp[3] = max(dp[3], dp[2] - prices[i]);
            dp[4] = max(dp[4], dp[3] + prices[i]);
        }
        return dp[4];
    }
};

188.?买卖股票的最佳时机 IV?

与上一题类似，索引为奇数时表示持有股票，索引为偶数是表示不持有股票

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() == 0) return 0;
        
        vector<int> dp(2*k+1, 0);
        for(int i=1;i<dp.size();i+=2)
        {
            dp[i]=-prices[0];
        }

        for (int i = 1; i < prices.size(); i++) {
            for(int j=1;j<dp.size();j++)
            {
                if(j%2==1)
                {
                    dp[j]=max(dp[j],dp[j-1]-prices[i]);
                }
                else
                {
                    dp[j]=max(dp[j],dp[j-1]+prices[i]);
                }
            }
            
        }
        return dp[2*k];
    }
};

?309.?买卖股票的最佳时机含冷冻期

?

每支股票的状态：

1.持有股票

2.未持有股票

• 延续未持有股票的状态
• 卖出股票
• 冷冻期?

一共有四种状态

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(),vector<int>(4,0));
        dp[0][0]=-prices[0];
        for(int i=1;i<prices.size();i++)
        {
            dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));
            dp[i][1]=max(dp[i-1][1],dp[i-1][3]);
            dp[i][2]=dp[i-1][0]+prices[i];
            dp[i][3]=dp[i-1][2];
        }
        return max(dp[dp.size()-1][1],max(dp[dp.size()-1][2],dp[dp.size()-1][3]));
    }
};

?