题目描述

给定一个数组,它的第 i 个元素是一支给定的股票在第 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
     随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。   
     因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]  输出: 0  解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

解法1

解法1采用dp解法,我们定义一个数组dp[3][|prices|], 其中dp[i][j]表示第j天前,发生了i次交易的最大收益。

我们可以写出状态转移方程dp[i][j] = max(dp[i][j-1], max{prices[j] – prices[k] + dp[i-1][k], 0<=k<j}), i<=0<3。

如果我们不在第j天卖出,用dp[i][j-1]表示我们忽略第j天的股价,那么最大收益和第j-1天一致,交易次数i也应该保持不变。如果我们选择在第j天卖出,那么我们需要寻找在[0, j-1]天的哪一天买入会使得在第j天卖出的收益最高,假设我们选择在第k天买入,那么第i次交易的收益为prices[j] – prices[k],此外我们还需要累积上第i-1次交易产生的收益dp[i-1][k].

最后,我们需要初始化dp矩阵使得dp[0][0…|prices|] = 0, dp[0..2][0] = 0,前者物理意义是如果不进行交易,无论历史股价是多少,收益都为0;后者因为第一天只能买入,所以收益是0。

图1 dp矩阵更新过程

图1绘制出了dp矩阵的更新过程,图中粗体字是每天的价格,红色箭头表示dp[i][j]数据来自于哪个位置。下面我们以i=1,j=5为例,来解释dp[1][5]的更新过程。

  • 如果在j=5不进行操作:那么我们的收益与j=4相等;
  • 如果在j=5卖出,需要寻找在哪一天买入使得在j=5卖出收益最大。

我们发现在j=5卖出,在j=4买入,有prices[5] – prices[4] + dp[0][4] = 3 – 0 + 0 = 3。即选择在j=5卖出能获得3收益,而选择在j=5不进行操作只能获得2收益,两个方案中取最大,更新dp[1][5] = 3。

由于算法我都是用Java实现,数组的初始值都为0,我们不需要初始化dp数组。根据上面的分析我们能编写出如下代码。时间复杂度为O(n^2),空间复杂度为O(n).

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;
        int[][] dp = new int[3][prices.length];
      
        for (int k = 1; k <= 2; k++) {
            for (int i = 0; i < prices.length; i++) {
                int maxProfit = 0;

                for (int j = 0; j < i; j++) {
                    // 我们可以不在第i天卖出dp[k][i - 1]
                    // 或者选择在第i天卖出prices[i] - prices[j] + dp[k - 1][j]
                    maxProfit = Math.max(maxProfit, Math.max(dp[k][i - 1], prices[i] - prices[j] + dp[k - 1][j]));
                }
                dp[k][i] = maxProfit;
            }
        }

        return dp[2][prices.length - 1];
    }
}

解法1优化

当使用dp方法时,若我们在第j天卖出,需要寻找在第k天买入(0<=k<j)使得第j天收益最大。在解法1中,我们通过遍历[0, j-1]每一天,寻找最大的prices[j] – prices[k] + dp[i][j],这就产生了O(n^2)的时间复杂度。

有一种很巧妙的方法,不必要对于每个j都向前回溯,因为我们碰到第j天时,已经经历了[0, j-1]天,我们通过之前的信息就能够对第j天作出正确的选择,这样能够使时间复杂度降低到O(n)。

我们使用临时变量tmpMax = max(dp[i-1][x] – prices[x]),0<=x<j。该变量的物理意义可以被理解为在第j天前的哪一天买入会使得手中的余额最大,因为dp[i-1][x]是买入第x天股票手中的收益,prices[x]是第x天的股价,我们选择在第x天买入股票,那么我们手中就剩下了dp[i-1][x] – prices[x]块钱。

当进行第i次交易时,我们选择在第j天卖出,我们用tmpMax记录下了j天前的某一天买入使得手中剩下的钱最多,那么就有dp[i][j] = max(dp[i][j-1], tmpMax + prices[j])。当dp[i][j]被更新后,不要忘记更新tmpMax。

图2 带有优化的矩阵更新过程

我们这次以i=2,j=5来分析dp[i][j]的更新过程。当j=5时, tmpMax (i=2)的值为2,物理意义是在第5天前的某一天进行买入,手中剩余的最大金额为2. 我们如果选择在j=5卖出,我们能获得prices[5]+tmpMax(i=2) = 3+2 = 5的收益。

根据上面的分析,我们能够编写出如下代码。时间复杂度为O(n),空间复杂度为O(n)。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;
        int[][] f = new int[3][prices.length];

        for (int i = 1; i <= 2; i++) {
            int tmpMax = f[i - 1][0] - prices[0];

            for (int j = 1; j < prices.length; j++) {
                //  prices[j] + tmpMax 在第j天卖出,那么应该寻找最低第买入价格
                // 巧妙第是,在第j天恰好经历了0-j-1,在这个时刻我们可以记录最低的买入价格
                f[i][j] = Math.max(f[i][j - 1], prices[j] + tmpMax);
                // tmpMax表示j天之前以最低的价格买入后,手中的余额
                tmpMax = Math.max(tmpMax, f[i - 1][j] - prices[j]);
            }
        }

        return f[2][prices.length - 1];
    }
}
pwrliang Algorithms, Dynamic Programming ,

Leave a Reply

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