LeetCode-188.Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most ktransactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.


使用动态规划

 1  public int maxProfit(int k, int[] prices) {//dp mytip
 2         if(null==prices||0==prices.length||0>=k){
 3             return 0;
 4         }
 5         int max =0;
 6         if(k>prices.length){//若k过大 优化
 7             for (int i = 0; i < prices.length-1; i++) {
 8                 if(prices[i]<prices[i+1]){
 9                     max+= prices[i+1]-prices[i];
10                 }
11             }
12         }
13         else{
14             int[][][] states = new int[prices.length][k+1][2];//状态表示第i个数在第j此交易中，有无股票时（0为无，1为有）的利益；//因为只保存上一个数时的利益，所以states可优化为[k+1][2]
15             for(int i=0;i<=k;i++){//初始化第1个数的状态
16                 states[0][i][1]=-prices[0];
17             }
18             for(int i=1;i<prices.length;i++){
19                 for(int j=0;j<=k;j++){
20                     if(j==0){
21                         states[i][j][0] = states[i-1][j][0];//防止j-1溢出
22                     }
23                     else{
24                         states[i][j][0] = Math.max(states[i-1][j][0],states[i-1][j-1][1]+prices[i]);
25                     }
26                     states[i][j][1] = Math.max(states[i-1][j][1],states[i-1][j][0]-prices[i]);
27                 }
28             }
29             for(int i=0;i<=k;i++){
30                 max = max>states[prices.length-1][i][0]?max:states[prices.length-1][i][0];
31             }
32         }
33         
34         return max;
35     }

优化空间

public int maxProfit(int k, int[] prices) {//dp my
        if(null==prices||0==prices.length||0>=k){
            return 0;
        }
        int max =0;
        if(k>prices.length){
            for (int i = 0; i < prices.length-1; i++) {
                if(prices[i]<prices[i+1]){
                    max+= prices[i+1]-prices[i];
                }
            }
        }
        else{
            int[][] states = new int[k+1][2];
            states[0][1] = -prices[0];
            for(int i=0;i<=k;i++){
                states[i][1]=-prices[0];
            }
            for(int i=1;i<prices.length;i++){
                for(int j=0;j<=k;j++){
                    states[j][1] = Math.max(states[j][1],states[j][0]-prices[i]);
                    if(j==0){
                        states[j][0] = states[j][0];
                    }
                    else{
                        states[j][0] = Math.max(states[j][0],states[j-1][1]+prices[i]);
                    }
                    
                }
            }
            for(int i=0;i<=k;i++){
                max = max>states[i][0]?max:states[i][0];
            }
        }
        
        return max;
    }