题目描述

给定一个数组,它的第 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 提交记录。

Leave a Reply

Your email address will not be published. Required fields are marked *