309. 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]

链接： http://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

题解：

股票题又来啦，这应该是目前股票系列的最后一题。卖出之后有cooldown，然后求multi transaction的最大profit。第一印象就是dp，但每次dp的题目，转移方程怎么也写不好，一定要好好加强。出这道题的dietpepsi在discuss里也写了他的思路和解法，大家都去看一看。不过我自己没看懂....dp功力太差了，反而是后面有一个哥们的state machine解法比较说得通。上面解法是based on一天只有一个操作，或买或卖或hold。也有一些理解为可以当天买卖的解法，列在了discuss里。看来题目真的要指定得非常仔细，否则读明白都很困难。

Time Complexity - O(n)， Space Complexity - O(n)

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0) {
            return 0;
        }
        int len = prices.length;
        int[] buy = new int[len + 1];       // before i, for any sequence last action at i is going to be buy
        int[] sell = new int[len + 1];      // before i, for any sequence last action at i is going to be sell
        int[] cooldown = new int[len + 1];  // before i, for any sequence last action at i is going to be cooldown
        buy[0] = Integer.MIN_VALUE;
        
        for(int i = 1; i < len + 1; i++) {
            buy[i] = Math.max(buy[i - 1], cooldown[i - 1] - prices[i - 1]);     // must sell to get profit
            sell[i] = Math.max(buy[i - 1] + prices[i - 1], sell[i - 1]);
            cooldown[i] = Math.max(sell[i - 1], Math.max(buy[i - 1], cooldown[i - 1]));
        }
        
        return Math.max(buy[len], Math.max(sell[len], cooldown[len]));
    }
}

使用State machine的

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length < 2) {
            return 0;
        }
        int len = prices.length;
        int[] s0 = new int[len];                // to buy
        int[] s1 = new int[len];                // to sell
        int[] s2 = new int[len];                // to rest
        s0[0] = 0;
        s1[0] = -prices[0];
        s2[0] = 0;
        
        for(int i = 1; i < len; i++) {
            s0[i] = Math.max(s0[i - 1], s2[i - 1]);         
            s1[i] = Math.max(s1[i - 1], s0[i - 1] - prices[i]);
            s2[i] = s1[i - 1] + prices[i];
        }
        
        return Math.max(s0[len - 1], s2[len - 1]);      // hold and res
    }
}

有机会还要简化space complexity，要看一看yavinci的解析。

题外话：

今天刚发现leetcode提交解答的页面加上了题目号，方便了不少，以前只是总目录有题号。这题跟我的情况很像。现在公司的policy是买入股票必须hold 30天，而且不可以买地产类股票...我觉得自己也没接触什么数据，就做不了短线，真的很亏..

Reference:

https://leetcode.com/discuss/72030/share-my-dp-solution-by-state-machine-thinking

http://fujiaozhu.me/?p=725

http://bookshadow.com/weblog/2015/11/24/leetcode-best-time-to-buy-and-sell-stock-with-cooldown/

https://leetcode.com/discuss/71391/easiest-java-solution-with-explanations

http://www.cnblogs.com/grandyang/p/4997417.html

https://leetcode.com/discuss/71246/line-constant-space-complexity-solution-added-explanation

https://leetcode.com/discuss/73617/7-line-java-only-consider-sell-and-cooldown

https://leetcode.com/discuss/71354/share-my-thinking-process