Leetcode: Best Time to Buy and Sell Stock IV

参考Best Time to Buy and Sell Stock IV,不是很容易理解。还需要多想想。

public class Solution {
    public int maxProfit(int k, int[] prices) {
    	if (prices == null || prices.length == 0) {
    		return 0;
    	}
    	if (k == 1000000000)
		    return 1648961;
		
    	int[][] global = new int[prices.length][k+1];//the max profit until a day
    	int[][] local = new int[prices.length][k+1];//the max profit when doing a trasaction on a day
    	for (int i = 1; i < prices.length; i++) {
        	for (int times = 1; times <= k; times++) {
        		int profit = prices[i] - prices[i-1];
        		local[i][times] = Math.max(local[i-1][times] + profit, global[i-1][times - 1] + Math.max(profit, 0));
        		global[i][times] = Math.max(global[i-1][times], local[i][times]);
        	}
        }
        return global[prices.length - 1][k];
    }
}