C++實現LeetCode(309.買股票的最佳時間含冷凍期)

Posted on by

[LeetCode] 309.Best Time to Buy and Sell Stock with Cooldown 買股票的最佳時間含冷凍期

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

  • You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
  • After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

這道題又是關於買賣股票的問題，之前有四道類似的題目Best Time to Buy and Sell Stock 買賣股票的最佳時間，Best Time to Buy and Sell Stock II 買股票的最佳時間之二， Best Time to Buy and Sell Stock III 買股票的最佳時間之三和Best Time to Buy and Sell Stock IV 買賣股票的最佳時間之四。而這道題與上面這些不同之處在於加入瞭一個冷凍期Cooldown之說，就是如果某天賣瞭股票，那麼第二天不能買股票，有一天的冷凍期。根據他的解法，此題需要維護三個一維數組buy, sell，和rest。其中：

buy[i]表示在第i天之前最後一個操作是買，此時的最大收益。

sell[i]表示在第i天之前最後一個操作是賣，此時的最大收益。

rest[i]表示在第i天之前最後一個操作是冷凍期，此時的最大收益。

我們寫出遞推式為：

buy[i]  = max(rest[i-1] - price, buy[i-1]) 
sell[i] = max(buy[i-1] + price, sell[i-1])
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

上述遞推式很好的表示瞭在買之前有冷凍期，買之前要賣掉之前的股票。一個小技巧是如何保證[buy, rest, buy]的情況不會出現，這是由於buy[i] <= rest[i]， 即rest[i] = max(sell[i-1], rest[i-1])，這保證瞭[buy, rest, buy]不會出現。

另外，由於冷凍期的存在，我們可以得出rest[i] = sell[i-1]，這樣，我們可以將上面三個遞推式精簡到兩個：

buy[i]  = max(sell[i-2] - price, buy[i-1]) 
sell[i] = max(buy[i-1] + price, sell[i-1])

我們還可以做進一步優化，由於i隻依賴於i-1和i-2，所以我們可以在O(1)的空間復雜度完成算法，參見代碼如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MIN, pre_buy = 0, sell = 0, pre_sell = 0;
        for (int price : prices) {
            pre_buy = buy;
            buy = max(pre_sell - price, pre_buy);
            pre_sell = sell;
            sell = max(pre_buy + price, pre_sell);
        }
        return sell;
    }
};

類似題目：

Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock

參考資料：

https://leetcode.com/discuss/71354/share-my-thinking-process

到此這篇關於C++實現LeetCode(309.買股票的最佳時間含冷凍期)的文章就介紹到這瞭,更多相關C++實現買股票的最佳時間含冷凍期內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：