714. Best Time to Buy and Sell S

感觉不像股票系列，倒是很像house rubery那个题。dp function的含义是"
sold[i]:第i天卖掉股票所能获取的最大利益
hold[i]:第i天稳住股票所能获取的最大利益
转换方程也很好理解：
sold[i] : 今天股票已卖出（不一定是今天卖，所以用sold)最大利益，应该是一直hold到昨天的最大利益，再加上今天的卖出价，减去手续费跟昨天就卖出的利益取最大值；
hold[i]: 今天保留的最大收益，可以是一直保留，也可以是昨天卖了，今天刚买回来所能产生的最大收益，两个取最大。

Follow-up (transition free)
Calculate everytime when prices[i] < prices[i+1] - cost 

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int max = 0;
        int[] sold = new int[prices.length]; //not possible
        int[] hold = new int[prices.length]; //meaning buy this stock
        sold[0] = 0;
        hold[0] = -prices[0];
        for (int i = 1; i < prices.length; i++){
            sell[i] = Math.max(sold[i - 1], hold[i - 1] + prices[i] - fee);
            hold[i] = Math.max(hold[i - 1], sold[i - 1] - prices[i]);
        }
        return Math.max(sold[prices.length - 1], hold[prices.length - 1]);
    }
}


optimize to O(1) space (like house rubery a lot)
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int max = 0;
        int sold = 0;
        int hold = -prices[0];
        for (int i = 1; i < prices.length; i++){
            int prevSold = sold;
            sold = Math.max(prevSold, hold + prices[i] - fee);
            hold = Math.max(hold, prevSold - prices[i]);
        }
        return Math.max(sold, hold);
    }
}