题目描述
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [2,4,1], k = 2 输出: 2 解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入: [3,2,6,5,0,3], k = 2 输出: 7 解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
尝试1 (OOM)
在上一篇博文123. 买卖股票的最佳时机 III，我们实现了最多允许2次交易的最大收益。本题目要求交易次数为k，我们将上一题的dp数组定义改为dp[k+1][|prices|]即可。我们可以得到如下代码。
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length <= 1)
return 0;
int[][] dp = new int[k + 1][prices.length];
for (int i = 1; i <= k; i++) {
for (int j = 1; j < prices.length; j++) {
int maxProf = 0;
for (int x = 0; x < j; x++) {
maxProf = Math.max(maxProf,
dp[i - 1][x] + prices[j] - prices[x]);
}
dp[i][j] = Math.max(dp[i][j - 1], maxProf);
}
}
return dp[k][prices.length - 1];
}
}
很遗憾，我无情的收到了OOM。失败测试用例的交易次数高达1000000000，这就意味着我们需要定义一个dp[1000000000][|prices|]的矩阵，这不OOM才怪。
最后执行的输入：1000000000 [106,373,495,46,359,919,906,440,783,583,784,73,238,701,972,308,165,774,990,675,737,990,713,157,211,880,961,132,980,136,285,239,628,221,…]
OOM的测试用例
尝试2 (TLE)
有了上一次失败的经验，我知道一定不能存储所有交易历史与对应的最大收益。我们通过观察状态转移方程，可以看出dp[i][j]仅依赖于dp[i][j-1]与dp[i-1][0…j-1]。因此，我们可以使用“双缓冲”的方法，定义而为数组dp[2][|prices|]。我们交替的使用dp[0]与dp[1]来存储最大收益。
在第21行，我们同时用了dp[0][|prices|-1]与dp[1][|prices|-1]的值，这是因为最终结果存储在dp[0][|prices|-1]还是dp[1][|prices|-1]取决于进行了奇数次交易还是偶数次交易。因此，我们需要对二者求最大值。通过上面的分析，我们能编写出下面的代码。
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length <= 1)
return 0;
int[][] dp = new int[2][prices.length];
for (int i = 1; i <= k; i++) {
for (int j = 1; j < prices.length; j++) {
int maxProf = 0;
for (int x = 0; x < j; x++) {
maxProf = Math.max(maxProf,
dp[(i - 1) % 2][x] + prices[j] - prices[x]);
}
dp[i % 2][j] = Math.max(dp[i % 2][j - 1], maxProf);
}
}
return Math.max(dp[0][prices.length - 1], dp[1][prices.length - 1]);
}
}
很遗憾，这次没有OOM，但是TLE了。失败的case仍然是k = 1000000000。不过没关系，我们在上一个帖子有优化方法，将时间复杂度O(k*n^2)降低到了O(k*n)。
尝试3 (TLE)
这次我使用了优化，将三层循环变成双层循环。那么时间复杂度也就从O(k*n^2)降低到了O(k*n)，具体的优化方法与解释见上一帖子。
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length <= 1)
return 0;
int[][] dp = new int[2][prices.length];
for (int i = 1; i <= k; i++) {
int tmpMax = dp[(i - 1) % 2][0] - prices[0];
for (int j = 1; j < prices.length; j++) {
dp[i % 2][j] = Math.max(dp[i % 2][j - 1], tmpMax + prices[j]);
tmpMax = Math.max(tmpMax, dp[(i - 1) % 2][j] - prices[j]);
}
}
return Math.max(dp[0][prices.length - 1], dp[1][prices.length - 1]);
}
}
很遗憾，虽然时间复杂度仅为O(k*n)，但是那个测试用例的k是在太大了，仍然TLE。
尝试4 (AC)
经过了3次失败，我实在想不出来优化方法了。我点开了评论区，发现需要分两种情况处理。
- k>=|prices| / 2，实际上相当于不限制交易次数
- k<|prices|，用“尝试3”中提到的方法解决
这里解释下为什么“k>=|prices| / 2相当于不限制交易次数”。假设我们有4天的股价，我们实际上最多只能做2笔交易。即，在第一天买出，第二天卖出（第一笔）；第三天买出，第四天卖出（第二笔）。以此类推，如果我们有|prices|天的股价，那么最多只能进行⌊|prices|/2⌋笔交易。如果k大于等与⌊|prices|/2⌋，就相当于不限制交易次数了。
对于不限制交易次数的条件，我们在“122. 买卖股票的最佳时机 II”这道题已经解决了，使用贪心法即可。我们通过上面的总结，根据k的大小分为两种情况分别处理，代码如下。
class Solution {
public int maxProfit(int k, int[] prices) { // TLE
if (prices.length <= 1)
return 0;
// 假设|prices| == 4, 那么你顶多能做两次交易，如果k >= prices.length / 2，实际上就相当于不限制交易次数了
if (k >= prices.length / 2) {
int res = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
res += prices[i] - prices[i - 1];
}
}
return res;
} else {
int[][] dp = new int[2][prices.length];
for (int i = 1; i <= k; i++) {
int tmpMax = dp[(i - 1) % 2][0] - prices[0];
for (int j = 1; j < prices.length; j++) {
dp[i % 2][j] = Math.max(dp[i % 2][j - 1], tmpMax + prices[j]);
tmpMax = Math.max(tmpMax, dp[(i - 1) % 2][j] - prices[j]);
}
}
return Math.max(dp[0][prices.length - 1], dp[1][prices.length - 1]);
}
}
}
在这个实现中，时间复杂度介于O(n)~O(k*n)直接。提交后直接AC，运行时间6ms，战胜 85.34 % 的 java 提交记录。