309. Best Time to Buy and Sell Stock with Cooldown (1)

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:

Input: [1,2,3,0,2]
Output: 3 
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Solution

先做好邏輯設計再針對edge處理

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        //在第i天， 交易的狀態可能是buy, sell, cooldown
        if(len <= 1)
            return 0;
        
        
        //buy[i] 表示第i+1天 以buy當作最後狀態的最大收益
        int[] buy = new int[len];
        
        //sell[i] 表示第i+1天 以sell or cooldown當作最後狀態的最大收益
        //ex:
        //    sell
        //sell cooldown
        int[] sell = new int[len];
        
        buy[0] = -prices[0];
        sell[0] = 0; //imposible
        buy[1] = Math.max(buy[0], -prices[1]);
        sell[1] = Math.max(sell[0], prices[1] - prices[0]);
        for(int i = 2; i < len; i++){
            int price = prices[i];
            buy[i] = Math.max(sell[i-2] - price, buy[i-1]);
            //有可能今天沒買但昨天買了(buy[i-1]) or 前天(i-2)以前賣了今天買了
            sell[i] = Math.max(buy[i-1] + price, sell[i-1]);
            //有可能今天沒賣但昨天賣了(sell[i-1]) or 昨天(i-1)以前買了今天賣了
        }
        
        return sell[len-1];
    }
}