算法-动态规划-股票交易

动态规划：求全局最优解：确认原问题与子问题，动态规划状态，状态转移方程，边界状态结值。

子问题：找到最终卖的收益最大值，或者max（最后的静默，最后的卖）

状态：买、卖的最大收益，第i次买、卖的最大收益 。

转化：sell=buy+a；buy=sell-a/-a

1. 股票交易-最多进行一次，无冷却期，手里最多一只股票
2.  股票交易-最多K次交易
3. 股票交易-1天的冷却期
4. 股票交易-需要交易费用
5. 股票交易-最多交易两次
6. 股票交易-条件很多

1. 最多进行一次

交易之后必须第二天才能在进行交易。如果在第i天卖出股票，则在[0-i-1]的一天中找到最小的买入价买入。

第i天的最大收益=max（历史最大收益，第i天进行交易后的收益）

public static int makeStoke(int[] A){
        if (A==null||A.length==0){
            return 0;
        }
        int maxM=-A[0];
        int pre=Integer.MAX_VALUE;
        for (int i = 1; i < A.length; i++) {
            pre=Math.min(pre,A[i-1]);
            maxM=Math.max(maxM,A[i]-pre);
        }
        return maxM;
    }

2. 最多K次交易

考虑第i天交易股票，那么找到[0,i-1]买股票，此次最大收益为max(这次不交易，第j天的收益+i天卖股票的钱-j天买股票的钱)

public static int maxProfit(int k, int[] prices) {
        /**
         当k大于等于数组长度一半时, 问题退化为贪心问题此时采用 买卖股票的最佳时机 II
         的贪心方法解决可以大幅提升时间性能, 对于其他的k, 可以采用 买卖股票的最佳时机 III
         的方法来解决, 在III中定义了两次买入和卖出时最大收益的变量, 在这里就是k租这样的
         变量, 即问题IV是对问题III的推广, t[i][0]和t[i][1]分别表示第i比交易买入和卖出时
         各自的最大收益
         **/
        if(k < 1) return 0;
        if(k >= prices.length/2) return greedy(prices);
        int[][] t = new int[k][2];
        for(int i = 0; i < k; ++i)
            t[i][0] = Integer.MIN_VALUE;
        for(int p : prices) {
            t[0][0] = Math.max(t[0][0], -p);
            t[0][1] = Math.max(t[0][1], t[0][0] + p);
            for(int i = 1; i < k; ++i) {
                t[i][0] = Math.max(t[i][0], t[i-1][1] - p);
                t[i][1] = Math.max(t[i][1], t[i][0] + p);
            }
        }
        return t[k-1][1];
    }
    private static int greedy(int[] prices) {
        int max = 0;
        for(int i = 1; i < prices.length; ++i) {
            if(prices[i] > prices[i-1])
                max += prices[i] - prices[i-1];
        }
        return max;
    }

3. 1天的冷却期     leetcode309

建立状态机，静默，buy，sell

详情：https://www.cnblogs.com/jdneo/p/5228004.html

 if (A == null || n <= 0) {
            return 0;
        }
        int[] S = new int[n];
        int[] buy = new int[n];
        int[] sell = new int[n];
        buy[0] = -A[0];
        for (int i = 1; i < n; i++) {
            S[i] = Math.max(S[i - 1], sell[i - 1]);
            buy[i] = Math.max(buy[i - 1], S[i - 1] - A[i]);
            sell[i] = buy[i] + A[i];
        }
        return Math.max(S[n - 1], sell[n - 1]);

4. 需要交易费用

//dp1[i]-第i天手里没有股票的最大收益: max(昨天手里没有股票，昨天有今天卖了)
//dp2[i]-第i天手里有股票的最大收益：max（昨天有，昨天没有今天买了）
    public static int makeStoke(int[] prices,int fee) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int n = prices.length;
        int[] dp1=new int[n];
        int[] dp2=new int[n];
        dp2[0]=-prices[0];
        for (int i = 1; i < n; i++) {
            dp1[i]=Math.max(dp1[i-1],dp2[i-1]+prices[i]-fee);
            dp2[i]=Math.max(dp2[i-1],dp1[i-1]-prices[i]);
        }
        return dp1[n-1];
    }

5. 最多交易两次

//最多交易；两次    O(n) O(n)
    public static int makeStokeK3(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int n = A.length;
        int[] firstBuy = new int[n];
        int[] firstSell = new int[n];
        int[] secondBuy = new int[n];
        int[] secondSell = new int[n];
        firstBuy[0]=-A[0];
        secondBuy[0]=-A[0];
        for (int i = 1; i < n; ++i) {
            firstBuy[i] =Math.max(firstBuy[i-1], -A[i]);
            firstSell[i]=Math.max(firstSell[i-1],firstBuy[i-1]+A[i]);
            secondBuy[i]=Math.max(secondBuy[i-1],firstSell[i-1]-A[i]);
            secondSell[i]=Math.max(secondSell[i-1],secondBuy[i-1]+A[i]);
        }
        return secondSell[n-1];
    }

    //最多交易；两次    O(n) O(1)
//    想要最后secondsell最大->secondbuy最大->firstBuy最大->firstBuy最大
    //若buy定住，则sell=buy+a(更大，重卖)；若buy=sell-a/-a，更小则重买。买卖都是累计值
    public static int makeStokeK4(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int n = A.length;
        int firstBuy=Integer.MIN_VALUE,firstSell=0;
        int secondBuy=Integer.MIN_VALUE,secondSell=0;
        for (int a:A) {
            if (firstBuy<-a){
                firstBuy=-a;
            }
            if (firstSell<firstBuy+a){
                firstSell=firstBuy+a;
            }
            if (secondBuy<firstSell-a){
                secondBuy=firstSell-a;
            }
            if (secondSell<secondBuy+a){
                secondSell=secondBuy+a;
            }
        }
        return secondSell;
    }