BiruLyu
7/6/2017 - 9:37 PM

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

public class Solution {
    public int maxProfit(int[] prices) {
        int sell = 0, pre_sell = 0, buy  = Integer.MIN_VALUE, pre_buy;
        for (int price : prices) {
            pre_buy = buy;
            buy = Math.max(pre_sell - price, pre_buy);
            pre_sell = sell;
            sell = Math.max(pre_buy + price, pre_sell);
        }
        return sell;
    }
}
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        int n = prices.length;
        int[] rest = new int[n];
        int[] buy = new int[n];
        int[] sell = new int[n];
        rest[0] = 0;
        buy[0] = -prices[0];
        sell[0] = Integer.MIN_VALUE;
        for(int i = 1; i < n; i++){
            buy[i] = Math.max(buy[i-1], rest[i-1]-prices[i]);
            sell[i] = buy[i-1] + prices[i];
            rest[i] = Math.max(rest[i-1], sell[i-1]);
        }
        return Math.max(rest[n-1], sell[n-1]);
    }
}