[leetcode309] Best Time to Buy a

    public int maxProfit(int[] prices) {
        /*
            重点在于表述状态转移方程，也就是从递归的角度描述，然后反向执行
            首先股票包含的状态为sell buy cool
            从递归的角度来看：
                股票在第i天能够执行的操作有 buy sell ,并且在卖和买之间有一天的cool,但是在买和卖之间同样存在隐藏的cool_hidden;
                判断第i天四种操作获取的最大利润
                buy[i]:cool[i-1]-price[i];
                cool_hidden[i]:cool_hidden[i-1];buy[i-1];
                sell[i]:cool_hidden[i-1]+price[i];buy[i-1]+price[i];
                cool[i]:sell[i-1];cool[i-1];
                这个状态太长，开始降维合并：
                首先，cool_hidden 可以合并到buy:hold操作就包含了buy和cool_hidden;
                cool也可以列合并到sell：unhold操作包含sell和cool

                hold[i]=max(hold[i-1],unhold[i-2]-price[i]);
                unhold[i]=max(unhold[i-1],hold[i-1]+price[i]);
        */
        int n = prices.length;
        if(n<2)
            return 0;
        int[] hold=new int[n];
        int[] unhold=new int[n];
        hold[0]=-prices[0];
        unhold[0]=0;
        hold[1]=Math.max(hold[0],unhold[0]-prices[1]);
        unhold[1]=Math.max(unhold[0],hold[0]+prices[1]);
        for(int i=2;i<n;i++){
            hold[i]=Math.max(hold[i-1],unhold[i-2]-prices[i]);
            unhold[i]=Math.max(unhold[i-1],hold[i-1]+prices[i]);
        }
        return Math.max(hold[n-1],unhold[n-1]);
                     
    }                     
}