309. Best Time to Buy and Sell S

自己的想法。虽然是O(n)，但是感觉肯定是麻烦了。
习惯把所有stock问题都用同一种模板了。

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1)    return 0;
        int n = prices.length;
        int dp[] = new int[n];
        dp[0] = 0;
        dp[1] = prices[1]-prices[0]>0? prices[1]-prices[0]:0;
        int max_tmp = prices[0] > prices[1] ? -prices[1]:-prices[0];
        
        for (int i=2; i<n; i++) {
            dp[i] = Math.max(max_tmp+prices[i], dp[i-1]);
            max_tmp = Math.max(max_tmp, dp[i-2]-prices[i]);
        }
        return dp[n-1];
    }
}

更好的，更简单的解法。空间O(1)

public class Solution {
    public int maxProfit(int[] prices) {
        int sell = 0, prev_sell = 0, buy = Integer.MIN_VALUE, prev_buy;
        for(int price : prices) {
            prev_buy = buy;
            buy = Math.max(prev_sell - price, prev_buy);
            prev_sell = sell;
            sell = Math.max (prev_buy + price, prev_sell);
        }
        return sell;
    }
}