C++中怎么利用LeetCode求買股票的最佳時(shí)間含冷凍期

C++中怎么利用LeetCode求買股票的最佳時(shí)間含冷凍期，相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策，為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法，通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。

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

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

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

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

我們寫出遞推式為：

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

上述遞推式很好的表示了在買之前有冷凍期，買之前要賣掉之前的股票。一個(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只依賴于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;
    }
};

看完上述內(nèi)容，你們掌握C++中怎么利用LeetCode求買股票的最佳時(shí)間含冷凍期的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！