Solution

1. 用local和global两个数组来实现dp local[i][j] = max(local[i - 1][j], global[i - 1][j - 1]) + diff

class Solution {
    /**
     * @param k: An integer
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int k, int[] prices) {
        // write your code here
        if (prices == null || prices.length == 0 || k <= 0) {
            return 0;
        } 

        int len = prices.length;
        if (k >= len / 2) {
            int sum = 0;
            for (int i = 1; i < len; i++) {
                sum += Math.max(0, prices[i] - prices[i - 1]);
            }

            return sum;
        }

        int[][] local = new int[len][k + 1];
        int[][] global = new int[len][k + 1];

        for (int i = 1; i < len; i++) {
            int diff = prices[i] - prices[i - 1];
            for (int j = 1; j <= k; j++) {
                local[i][j] = Math.max(local[i - 1][j], global[i - 1][j - 1]) + diff;
                global[i][j] = Math.max(local[i][j], global[i - 1][j]);
            }
        }

        return global[len - 1][k];
    }
};