题解 | #买卖股票的最好时机(四)#

import java.util.*;


public class Solution {
    public int maxProfit (int[] prices, int k) {
        int n = prices.length;
        if(k > n/2){
            return maxProfitAny(prices,k);
        }else{
            return maxProfitK(prices,k);
        }
        
    }
    private int maxProfitAny(int[] prices,int k){
        int n = prices.length;
        int[][] dp = new int[n][2];
        for(int i = 0;i<n;i++){
            if(i-1 == -1){
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }
    private int maxProfitK(int[] prices, int maxK){
        int n = prices.length;
        int[][][] dp = new int[n][maxK+1][2];
        for(int i = 0;i<n;i++){
            dp[i][0][0] = 0;
            dp[i][0][1] = Integer.MIN_VALUE;
        }
        for(int i = 0;i<n;i++){
            for(int k = maxK;k >=1;k--){
                if(i-1 == -1){
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue;
                }
                dp[i][k][0] = Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
                dp[i][k][1] = Math.max(dp[i-1][k-1][0]-prices[i],dp[i-1][k][1]);
            }
        }
        return dp[n-1][maxK][0];
    }
}