📚188. Best Time to Buy and Sell

挺难的题。recursive需要好好想。

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if(k<=0 || prices == null || prices.length==0)
            return 0;
        int len = prices.length;
        
        if(k >= len/2) {
            int max_prof = 0;
            for(int j=1; j<len; j++) {
                if(prices[j] > prices[j-1])
                    max_prof += prices[j]-prices[j-1];
            }
            return max_prof;
        }
        
        int dp[][] = new int[k+1][len];
        
        for(int i=1; i<=k; i++) {
            int max_tmp = dp[i-1][0] - prices[0];
            for(int j=1; j<len; j++) {
                dp[i][j] = Math.max(dp[i][j-1], max_tmp + prices[j]);
                max_tmp = Math.max(max_tmp, dp[i-1][j] - prices[j]);
            }
        }
        
        return dp[k][len-1];
    }
}