Description

Say you have an array for which thei_th element is the price of a given stock on day_i.

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

Notice

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

Example

Given prices =[4,4,6,1,1,4,2,5], and k =2, return6.

Solution

1. 用local和global两个数组来实现dp local[i][j] = Math.max(local[i - 1][j], global[i - 1][j - 1]) + diff 分为两个情况1> i- 1和i点连在一起属于同一个transaction内，2> i-1买进i卖出成为一个独立的transaction。

2. 当k>=len/2时，相当于每个点都要做出操作，所以把获利的天数加起来就好了。因为至多进行k次操作，所以加的时候要作出判断，不要把亏本的买卖加进来。

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];
    }
};