[leetcode]Best Time to Buy and S

1. Best Time to Buy and Sell Stock
   reqest:只允许购买一次股票，即只能买入卖出一次

构建类似马尔科夫链的转态转移函数：
每个交易日可以又两种选择 buy 和sell
而buy和sell之间存在着先后关系，buy为第一次买入得到的最大利润，一定是负值，sell为第一次卖出得到的最大利润。

buy(i)=Math.max(buy(i-1),-prices[i]);
//实质是保存目前为止的最小交易值
sell(i)=Math.max(sell(i-1),buy(i-1)+prices[i]);
//在不断更新最小交易值的同时，不断判断目前交易天卖出是否是最大值。
必须先更新sell值，再更新buy,目的是为了利用上次迭代的buy去更新sell值

class Solution {
    public int maxProfit(int[] prices) {
        int buy=Integer.MIN_VALUE;
        int sell=0;
        int n=prices.length;
        for(int i=0;i<n;i++){
            sell=Math.max(sell,buy+prices[i]);
            buy=Math.max(buy,-prices[i]);
            
        }
        return sell;
        
    }
}

2. Best Time to Buy and Sell Stock III
   request:可以最多两次次买入卖出

利用上面的思路，找状态转移方程，可以写出

sell2=Math.max(sell2,buy2+prices[i]);
//第二次买出的最大利润
buy2=Math.max(buy2,sell1-prices[i]);
//第二次买入的最大利润
sell1=Math.max(sell1,buy1+prices[i]);
//利用目前最大的买入利润得到第一次卖出的最大利润
buy1=Math.max(buy1,-prices[i]);
//保存第一次买入的最大利润，也就是交易额最小
所有变量是按照转态转移方程去不断更新优化，获得最佳值，

3. Best Time to Buy and Sell Stock II
   requeat:可以多次买入买出，但每次买入必须在上一次卖出

   如果利用上述思路，继续使用状态转移方程，那么因为交易次数的不确定，最后得到的无数的状态转移方程，不可能实现，那么就要把状态转移方程合并成符合题目要求的样子
   可以看到在Best Time to Buy and Sell Stock,单次交易的解决方法，那么无数次交易可以看成是无数次单次交易，先找到在某个时刻点买入的股票能连续获利的的最大值，一旦哪天卖出是相较上一天是亏本，则得到了一次买卖的收入，然后再次重复
   其中的关键就是连续获利，也就是判断当天交易额是否比上一天高，高说明可以持续获利，低则说明买入的股票在上一天得到顶峰，上一天可以卖出，然后在寻找下一个连续获利的序列
   与一次买卖最大的区别在于，每次卖出获利不是全局最优值，但是无数个局部最优值的叠加，贪婪算法。

class Solution {
    public int maxProfit(int[] prices) {
        int min=Integer.MAX_VALUE;
        int max=0;
        int n = prices.length;
        for(int i=1;i<n;i++){
           if(prices[i]>prices[i-1])
               max+=prices[i]-prices[i-1]；
        }
        return max;
    }
}

第二种方法，就是利用状态转移方程，对每次交易日的两种选择判断执行，这里的buy包含两种意思，之前卖了，当前天买入，或是之前买入了，然后一直保持在手里

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

4. Best Time to Buy and Sell Stock IV
   request：
   指定交易次数k,然后求最大利润。

同样的从一次买卖中寻找线索
二次买卖是在每个交易日更新二次交易值，那么K次买卖是不是能更新k次交易日，这个思路明显是正确的。

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        
        if(k==0||n<2)
            return 0;
        if (n/2 < k){
            return quickSolve(prices);
//因为当k次交易大于交易日的一般，也就是每天交易都打不到k次交易，则就可以按照无数次交易贪婪得到无数局部最优解的叠加
        }
        int[] hold = new int[k+1];
        for(int i=0;i<=k;i++){
            hold[i]=Integer.MIN_VALUE;
        }

        int[] unhold = new int[k+1];
        hold[1]=Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            for(int j=1;j<=k;j++){
                unhold[j]=Math.max(unhold[j],hold[j]+prices[i]);
                hold[j]=Math.max(hold[j],unhold[j-1]-prices[i]);
                
               //在每个交易日对k个买卖的值执行更新
                
            }
        }
        return unhold[k];
    }
    int quickSolve(int[] prices) {
        int len = prices.length, profit = 0;
        for (int i = 1; i < len; i++)
            // as long as there is a price gap, we gain a profit.
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit;
    }

}

5. Best Time to Buy and Sell Stock with Cooldown
   request：可以多次交易，但是在卖出之后又一天的冷冻期不能买入
   同样利用状态转移方程，

    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]);
                     
    }                     
}
6. Best Time to Buy and Sell Stock with Transaction Fee
request:每笔交易需要手续费，但不限交易次数

class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int[] hold = new int[n];
int[] unhold=new int[n];
unhold[0]=0;
hold[0]=-prices[0];
for(int i=1;i<n;i++){
unhold[i]=Math.max(unhold[i-1],hold[i-1]+prices[i]-fee);
hold[i]=Math.max(hold[i-1],unhold[i-1]-prices[i]);
}
return unhold[n-1];
}
}