[LeetCode]Best Time to Buy and Sell Stock with Coo

xcc3641 發(fā)布于2019-08-14 15:08 / 777人閱讀

摘要：分析因?yàn)楫?dāng)前日期買賣股票會(huì)受到之前日期買賣股票行為的影響，首先考慮到用解決。所以我們可以用兩個(gè)數(shù)組分別記錄當(dāng)前持股跟未持股的狀態(tài)。

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]

分析

因?yàn)楫?dāng)前日期買賣股票會(huì)受到之前日期買賣股票行為的影響，首先考慮到用DP解決。

這道題比較麻煩的是有個(gè)cooldown的限制，其實(shí)本質(zhì)也就是買與賣之間的限制。對(duì)于某一天，股票有三種狀態(tài): buy, sell, cooldown, sell與cooldown我們可以合并成一種狀態(tài)，因?yàn)槭掷镒罱K都沒股票，最終需要的結(jié)果是sell，即手里股票賣了獲得最大利潤(rùn)。所以我們可以用兩個(gè)DP數(shù)組分別記錄當(dāng)前持股跟未持股的狀態(tài)。然后根據(jù)題目中的限制條件，理清兩個(gè)DP數(shù)組的表達(dá)式。

對(duì)于當(dāng)天最終未持股的狀態(tài)，最終最大利潤(rùn)有兩種可能，一是今天沒動(dòng)作跟昨天未持股狀態(tài)一樣，二是昨天持股了，今天賣了。所以我們只要取這兩者之間最大值即可，表達(dá)式如下：

sellDp[i] = Math.max(sellDp[i - 1], buyDp[i - 1] + prices[i]);

對(duì)于當(dāng)天最終持股的狀態(tài)，最終最大利潤(rùn)有兩種可能，一是今天沒動(dòng)作跟昨天持股狀態(tài)一樣，二是前天還沒持股，今天買了股票，這里是因?yàn)閏ooldown的原因，所以今天買股要追溯到前天的狀態(tài)。我們只要取這兩者之間最大值即可，表達(dá)式如下：

buyDp[i] = Math.max(buyDp[i - 1], sellDp[i - 2] - prices[i]);

最終我們要求的結(jié)果是

sellDp[n - 1] 表示最后一天結(jié)束時(shí)手里沒股票時(shí)的累積最大利潤(rùn)

當(dāng)然，這里空間復(fù)雜度是可以降到O(1)的，具體見第二種代碼實(shí)現(xiàn)。

復(fù)雜度

time: O(n), space: O(n)

代碼

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        // 表示當(dāng)天最終未持股的情況下，當(dāng)天結(jié)束后的累計(jì)最大利潤(rùn)
        int[] sellDp = new int[prices.length];
        // 表示當(dāng)天最終持股的情況下，當(dāng)天結(jié)束后的累計(jì)最大利潤(rùn)
        int[] buyDp = new int[prices.length];
        
        // 考慮初始情況
        buyDp[0] = -prices[0];
        sellDp[0] = 0;
        for (int i = 1; i < prices.length; i++) {
            sellDp[i] = Math.max(sellDp[i - 1], buyDp[i - 1] + prices[i]);
            if (i >= 2) {
                buyDp[i] = Math.max(buyDp[i - 1], sellDp[i - 2] - prices[i]);
            } else {
                buyDp[i] = Math.max(buyDp[i - 1], -prices[i]);
            }
        }
        return sellDp[prices.length - 1];
    }
}

代碼(O(1) space)

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
    
        int currBuy = -prices[0];
        int currSell = 0;
        int prevSell = 0;
        for (int i = 1; i < prices.length; i++) {
            int temp = currSell;
            currSell = Math.max(currSell, currBuy + prices[i]);
            if (i >= 2) {
                currBuy = Math.max(currBuy, prevSell - prices[i]);
            } else {
                currBuy = Math.max(currBuy, -prices[i]);
            }
            prevSell = temp;
        }
        return currSell;
    }
}