Best Time to Buy and Sell Stock IV(Hard)

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

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

题意：用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。最多交易k次，手上最多只能持有一支股票，求最大收益。

不允许同时参与多个交易（也就是说，买入股票之前必须先卖出）

一次交易是指一次完整的买入和卖出

定义维护量：

global[i][j]:在到达第i天时最多可进行j次交易的最大利润，此为全局最优

local[i][j]:在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优

global[i][j]=max(local[i][j],global[i-1][j])

也就是取当前局部最好的，或过往全局最好的中大的那个（因为最后一次交易如果包含当前天一定在局部最好的里面，否则一定在过往全局最优的里面）。

local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)

情况1：第i-1天后，共交易了j-1次（global[i-1][j-1]），因此为了满足“第i天过后共进行了j次交易，且第i天必须进行交易”的条件：我们可以选择1：当第i天的价格高于第i-1天（即diff > 0,在第i-1天买入，然后再第i天卖出（diff）；当第i天的价格低于第i-1天（即diff < 0）选择在第i天买入，然后同样在第i天卖出（收益为0）。

情况2：在第i-1天时，恰好已经交易了j次（local[i-1][j]），那么如果i-1天到i天再交易一次：即在第i-1天买入，第i天卖出（diff），则这不并不会增加交易次数！【例如我在第一天买入，第二天卖出；然后第二天又买入，第三天再卖出的行为和第一天买入，第三天卖出的效果是一样的，其实只进行了一次交易！因为有连续性】

最多允许 k 次交易，由于一次增加收益的交易至少需要两天，故当 k >= n/2时，此题退化为卖股票的第二道题，即允许任意多次交易。当 k < n/2 时，使用动规来求解

代码：时间O(nk)，空间O(nk)。

public int maxProfit(int k, int[] prices) {
        if (prices.length < 2) return 0;

        int days = prices.length;
        if (k >= days/2) return maxProfit2(prices);

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

        for (int i = 1; i < days ; i++) {
            int diff = prices[i] - prices[i - 1];

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

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


    public int maxProfit2(int[] prices) {
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }

        return maxProfit;
    }

我们知道，动规所用的二维辅助数组可以降为一维的，即只用大小为k的一维数组记录到达第i天时的局部最优解和全局最优解。需要注意的是，由于第i天时交易k次的最优解依赖于第i-1天时交易k-1次的最优解，所以数组更新应当从后往前（即从k到1）更新。

代码：时间O(nk)，空间O(k)。

public int maxProfit(int k, int[] prices) {
        if (prices.length < 2) return 0;
        if (k >= prices.length/2) return maxProfit2(prices);

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

        for (int i = 1; i < prices.length ; i++) {
            int diff = prices[i] - prices[i - 1];

            for (int j = k; j > 0; j--) {
                local[j] = Math.max(global[j - 1]+ Math.max(diff, 0), local[j] + diff);
                global[j] = Math.max(global[j], local[j]);
            }
        }

        return global[k];
    }


    public int maxProfit2(int[] prices) {
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }

        return maxProfit;
    }

References:

1 Best Time to Buy and Sell Stock I II III IV

Best Time to Buy and Sell Stock IV