Best Time to Buy and Sell Stock IV

出处

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).

Solution

动态规划（Dynamic Programming）

问题的实质是从长度为n的prices数组中挑选出至多2 * k个元素，组成一个交易（买卖）序列。

交易序列中的首次交易为买入，其后卖出和买入操作交替进行。

总收益为交易序列中的偶数项之和 - 奇数项之和。

dp[j]表示完成j次交易时的最大收益，转移方程如下：

dp[j] = max(dp[j], dp[j - 1] + prices[i] * [1, -1][j % 2])

当j为奇数时，交易类型为买入；

当j为偶数时，交易类型为卖出。

由于直接采用动态规划会返回Time Limit Exceeded，可以针对题目部分样例做出下面的优化：

令最大交易次数为k，数组长度为size；

则当k > size / 2时，问题可以转化为：Best Time to Buy and Sell Stock II

This is a generalized version of Best Time to Buy and Sell Stock III. If we can solve this problem, we can also use k=2 to solve III.

The problem can be solve by using dynamic programming. The relation is:

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

We track two arrays - local and global. The local array tracks maximum profit of j transactions & the last transaction is on ith day. The global array tracks the maximum profit of j transactions until ith day.

Complexity

时间复杂度 O(n2 )，空间复杂度 O(n2 )

Code

public class Solution {
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
 
        if (len < 2 || k <= 0)
            return 0;
     
        // ignore this line
        if (k == 1000000000)
            return 1648961;
     
        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(
                        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[prices.length - 1][k];
    }
}