Leetcode — 309. Best Time to Buy and Sell Stock with Cooldown (中文)

問題連結: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

給予一陣列, 第i位置則顯示在Day i時的股票價錢, 回傳你在這幾天可賺到的最高利潤, 這幾天之中買進買出的次數不受限制, 但有幾個條件 —

• 在買股票之前, 需把手上的股票賣掉 (也就是買進之後只能賣出, 手上不能有一張以上股票)
• 在賣掉股票後至少要休息一天(也就是需cool down)才能買股票, 不能賣股票隔天馬上買

範例
Input: [1,2,3,0,2]
Output: 3 
最高利潤的買法: [買, 賣, 休息, 買, 賣]

想法:

我們目前已經練習了幾個股票問題, 像是 Leetcode — 122. Best Time to Buy and Sell Stock II (中文)跟這題Leetcode — 123. Best Time to Buy and Sell Stock III (中文)
前面幾題都是 頂多限制交易次數, 這次雖然像122題一樣沒限制交易次數, 但交易之間不能接連著, 一定要注意cooldown

我們這次也仍然可以用動態規劃dynamic programming來解這題, 因為我們仍然需要依靠著前幾天的各種動作來判斷今天可做的動作(買, 賣,或休息)

最簡單跟最直覺的方法就是用暴力解, 我們用一個陣列來存我們在Day i的時候可賺到的最高利潤

我們在每天會做的事情就是看我們今天要決定哪個動作能得到目前最高利潤: 賣股票或休息什麼都不做
⚠️不考慮買的原因是因為現在我們就是希望找到最高利潤, 但如果買的話 利潤反而減少, 我們的政策是 在 當我們決定今天要賣的時候, 才往前找最佳買進日

1. 若我們選擇今天休息什麼都不做, 代表我們今天的利潤不減也不增, 因此今天可得的最高利潤就會跟前一天一樣
2. 若我們選擇賣出股票, 代表我們就要找在這天之前的每一天, 找出最佳買進日Day j, 當我們找到Day j時, 我們可得的最高利潤除了這一次交易(Day j買進 Day i賣出)以外, 還可以加上在Day j的兩天前所得的最高利潤 當作我們在Day i時的最高利潤
   👷為何說若我們選買在Day j時, 可以把利潤加到我們在Day (j-2)的最高利潤視為Day i的利潤: 因為當我們決定我們這次的交易是在Day j跟Day i之前時, 代表我們允許前一個交易需要跟我們這次交易有一個休息的天數, 而最保險就是我們選拿Day (j-2)最高的利潤, 因為我們不需在意我們在Day (j-2)那天到底有沒有賣股票而違反我們的條件

以下為 29ms 程式碼, 贏過 7% —

public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n<=1)
            return 0;
        int[] dp = new int[n];
        if(prices[1]>prices[0])
            dp[1] = prices[1]-prices[0];
        for(int i=2;i<n;i++)
        {
            int maxProfit = dp[i-1]; //cooldown
            //find buy day
            for(int j=0;j<i;j++)
            {
                if(prices[j]>prices[i])
                    continue;
                int preProfit = j>1? dp[j-2]:0; 
                maxProfit = Math.max(maxProfit,
                                    preProfit+prices[i]-prices[j]);
            }
            dp[i] = maxProfit;
        }
        return dp[n-1];
    }

時間複雜度: O(n²); 空間複雜度: O(n)

我們有沒有辦法能在時間O(n)內完成?

程式邏輯:

因為我們在每天決定要賣出時, 都又額外花O(n)時間來找我們的買進日, 有沒有辦法我們可以省下這個步驟?

這次, 我們每一天將會考慮當我們在這一天Day i買, 賣, 休息的時候可得的最大利潤, 我們將會用三個不同的陣列來儲存 到Day i 為止, 若我們最後一個動作是買/賣/休息 的時候, 我們可得到的最大利潤為何

當我們決定我們要在今天Day i做買/賣/休息的時候, 因為我們也需要延續前面所累積的最大利潤們, 因此我們也要想 當我們做某個選擇的時候 前一天Day (i-1)時的最大利潤為何, 若我們發現當我們今天選擇買/賣/休息時, 不能比 "在前一天的時候 最後一個動作為買/賣/休息 可賺到的利潤" 還高時, 我們就會放棄在Day i進行我們選的那個動作, 以免破壞"現有行情"

🚧在各別的買/賣/休息 陣列中 (各自命名為buy/sell/cooldown), 我們將記錄當各自到Day i時最後一個動作是 買/賣/休息的時候, 可得的最高利潤

3種我們要在Day i時考慮的情況:

1. 若我們考慮今天買股票, 代表直到昨天, 最後的動作一定只能是休息, 因為我們不可以在昨天買或賣的情況下買股票
   所以我們這時候就要比較 "若我們昨天休息而今天買" 的利潤 與 "若我們昨天買"的利潤誰大誰小, 來決定我們今天要不要買
2. 若我們考慮今天賣股票, 代表直到昨天, 最後的動作一定只能是買股票, 因為一定要買過才有東西賣
   所以我們這時候就要比較 "若我們今天賣上次買的股票" 的利潤 與 "若我們昨天賣股票"的利潤誰大誰小, 來決定我們今天要不要賣
3. 若我們決定今天休息, 代表直到昨天, 最後的動作可能是賣或者休息, 因此我們休息的利潤會同昨天休息的利潤, 只要比較"昨天最後動作是賣"的最高利潤 與"昨天最後動作是休息" 的最高利潤的大小, 就可以決定今天要不要休息

以下為1ms程式碼, 贏過 55% —

public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n<=1)
            return 0;
        int[] buy = new int[n];
        int[] sell = new int[n];
        int[] cooldown = new int[n];
        
        //no choice on day 0
        buy[0] = -prices[0];
for(int i=1;i<n;i++)
        {
            buy[i] = Math.max(buy[i-1], cooldown[i-1]-prices[i]);
            sell[i] = Math.max(sell[i-1], prices[i]+buy[i-1]);
            cooldown[i] = Math.max(cooldown[i-1], sell[i-1]);
        }
        return Math.max(sell[n-1],cooldown[n-1]);

時間複雜度: O(n); 空間複雜度: O(n)

沿用上述的程式邏輯, 因為我們其實只是每次都拿陣列們的第i-1的數字, 我們也可以直接用三個變數來代替三個陣列來節省空間複雜度

以下為0ms程式碼, 贏過 100% —

public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n<=1)
            return 0;
        int buy = -prices[0];
        int sell = 0;
        int cooldown = 0; 
        for(int i=1;i<n;i++)
        {
            int pre_buy = buy, pre_sell = sell;
            int pre_cooldown = cooldown;
            buy = Math.max(pre_buy, pre_cooldown-prices[i]);
            sell = Math.max(pre_sell, prices[i]+pre_buy);
            cooldown = Math.max(pre_cooldown,pre_sell);
        }
        return Math.max(sell,cooldown);
    }

時間複雜度: O(n); 空間複雜度: O(1)