[LeetCode] 309.Best Time to Buy and Sell Stock with Cooldown 買(mǎi)股票的最佳時(shí)間含冷凍期

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)于買(mǎi)賣(mài)股票的問(wèn)題，之前有四道類(lèi)似的題目Best Time to Buy and Sell Stock 買(mǎi)賣(mài)股票的最佳時(shí)間，Best Time to Buy and Sell Stock II 買(mǎi)股票的最佳時(shí)間之二， Best Time to Buy and Sell Stock III 買(mǎi)股票的最佳時(shí)間之三和Best Time to Buy and Sell Stock IV 買(mǎi)賣(mài)股票的最佳時(shí)間之四。而這道題與上面這些不同之處在于加入了一個(gè)冷凍期Cooldown之說(shuō)，就是如果某天賣(mài)了股票，那么第二天不能買(mǎi)股票，有一天的冷凍期。根據(jù)他的解法，此題需要維護(hù)三個(gè)一維數(shù)組buy, sell，和rest。其中：

buy[i]表示在第i天之前最后一個(gè)操作是買(mǎi)，此時(shí)的最大收益。

sell[i]表示在第i天之前最后一個(gè)操作是賣(mài)，此時(shí)的最大收益。

rest[i]表示在第i天之前最后一個(gè)操作是冷凍期，此時(shí)的最大收益。

我們寫(xiě)出遞推式為：

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])

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

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

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只依賴(lài)于i-1和i-2，所以我們可以在O(1)的空間復(fù)雜度完成算法，參見(jiàn)代碼如下：

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;
    }
};

類(lèi)似題目：

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.買(mǎi)股票的最佳時(shí)間含冷凍期)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)買(mǎi)股票的最佳時(shí)間含冷凍期內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論