# 309 Best Time to Buy and Sell Stock with Cooldown

給一個整數矩陣prices，表示每天買進/賣出的價格，問可獲得的最高利潤為何。和基礎的賣股票問題不同的是下面兩條規則：

1. 必須先賣掉手上的股票才能再買進
2. 賣出之後要休息一天，才可以買或賣

Concept 最基本的買賣股票問題的解法為用一dp矩陣存每日的最高可能獲利 可以用類似的方法，只是改成用三個矩陣buy, sell, rest記錄當天進行這三個行為的最大可能獲利。

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

其中rest[i]的利潤會和sell[i-1]相同，可將上三式簡化成兩式

buy[i] = max(sell[i-2] - price, buy[i-1])
sell[i] = max(buy[i-1] + price, sell[i-1])

1維dp可以簡化為用兩個變數實現，就得到以下結果

Code

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;

        int sell = 0, prev_sell = 0;
        int buy = Integer.MIN_VALUE, prev_buy = Integer.MIN_VALUE;

        for(int i=0; i<len; i++){
            prev_buy = buy;
            buy = Math.max(prev_sell-price[i], prev_buy);
            prev_sell = sell;
            sell = Math.max(prev_buy+price[i], prev_sell);
        }

        return sell;
    }
}