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

Say you have an array for which the i^th 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]

這道題又是關(guān)于買賣股票的問題，之前有四道類似的題目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之說，就是如果某天賣了股票，那么第二天不能買股票，有一天的冷凍期。根據(jù)他的解法，此題需要維護(hù)三個一維數(shù)組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]的情況不會出現(xiàn)，這是由于buy[i] <= rest[i]， 即rest[i] = max(sell[i-1], rest[i-1])，這保證了[buy, rest, buy]不會出現(xiàn)。

另外，由于冷凍期的存在，我們可以得出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])

我們還可以做進(jìn)一步優(yōu)化，由于i只依賴于i-1和i-2，所以我們可以在O(1)的空間復(fù)雜度完成算法，參見代碼如下：

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

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(309.買股票的最佳時間含冷凍期)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)買股票的最佳時間含冷凍期內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論