[LeetCode]Best Time to Buy and Sell Stock IV

根据Max Subarray III我们可以知道这一题是有时间O(k* n)，空间O(k* n)的解法的。GlobalMax[i][j]代表进行i次操作，在前j天之内的最大利润；localMax[i][j]代表代表进行i次操作，在前j天之内的最大利润，并且最后一次操作完成在第j天。DP方程如下：

• GlobalMax[i][j] = max(GlobalMax[i][j - 1], localMax[i][j]);
• localMax[i][j] = max(GlobalMax[i - 1][k] + price[j] - price[k]), 其中0 <= k <= j；

我们可以看到max(GlobalMax[i - 1][k] + price[j] - price[k])是取决于max(GlobalMax[i - 1][k] - price[k])这个值的，我们只要一直维护这个的最大值就可以了（这个值的代表什么笔者并不明确），这个比Max Subarray III的线性做法更直观，我们可以在线性时间构建GlobalMax[i]。代码如下：

我们可以只用一维数组解决这个问题，这样空间复杂度可以优化到O(n)，但是这样仍然过不了test case最后几组数据，这是因为那几组数据k远远大于n，这样导致整体的时间复杂度k * n很高，但是值得注意的是，当允许交易次数多于n / 2的时候（也就是第一天买，第二天卖，第三天买，第四天卖。。。我们不会第一天买，第二天卖，然后第二天买，第三天卖，这样的话就相当于第一天买第三天卖），我们永远可以达到给定prices数组的最大利润，这样的话，题目就变为Best Time to Buy and Sell Stock II，我们可以在O(n)的时间内解决。所以我们特别check这种情况即可，代码如下：