买卖股票的最佳时机 III

难度: Hard

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

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

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

示例 1:

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

示例 2：

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

示例 3：

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

示例 4：

输入：prices = [1]
输出：0

提示：

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁵

Submission

运行时间: 2012 ms

内存: 59.9 MB

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = dp = [ [[0, 1] for _ in range(3)]  for _ in range(n+1)]
        for i in range(1, n+1):
            for k in range(1, 3):
                # base case
                if i == 1:
                    dp[i-1][k][0] = 0
                    dp[i-1][k][1] = float('-inf')
                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i-1])
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i-1])
        return dp[-1][2][0]

Explain

这个题解使用动态规划的思想。它定义了一个三维的 DP 数组，其中 dp[i][k][0] 表示在第 i 天结束时，已经完成 k 次交易，并且当前没有持有股票的最大利润；dp[i][k][1] 表示在第 i 天结束时，已经完成 k 次交易，并且当前持有股票的最大利润。通过遍历价格数组，不断更新 DP 数组，最终 dp[-1][2][0] 就是完成两笔交易可以获得的最大利润。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        # 定义 DP 数组
        dp = [ [[0, 1] for _ in range(3)] for _ in range(n+1)]
        
        for i in range(1, n+1):  # 遍历价格数组
            for k in range(1, 3):  # 最多完成两次交易
                # base case，第一天的状态
                if i == 1:
                    dp[i-1][k][0] = 0
                    dp[i-1][k][1] = float('-inf')
                
                # 状态转移方程
                # 第 i 天没有持有股票的最大利润，可以从两个状态转移而来：
                # 1. 第 i-1 天没有持有股票
                # 2. 第 i-1 天持有股票，然后在第 i 天卖出
                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i-1])
                
                # 第 i 天持有股票的最大利润，可以从两个状态转移而来：
                # 1. 第 i-1 天持有股票
                # 2. 第 i-1 天完成了 k-1 次交易，然后在第 i 天买入
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i-1])
                
        # 最终结果是最后一天完成两次交易且没有持有股票的最大利润
        return dp[-1][2][0]

Explore

在该动态规划解法中，使用三维数组 dp[i][k][0] 和 dp[i][k][1] 来存储状态，是为了明确地表示在每一天结束时的最大利润，考虑到交易次数和持有状态的不同情况。第一维 i 表示第 i 天，用于追踪截至到当前天的交易情况。第二维 k 表示已经完成的交易次数（最多为2次），这是因为题目限定了交易次数。第三维的 0 和 1 分别表示当前不持有股票（0）和持有股票（1）的状态。这样的分维设计使得问题的每一个状态都能够被清晰地记录和更新。

基础情况（base case）的设置是为了处理动态规划中的初始状态，使得后续状态能够正确地依据这些基础条件进行转移。对于 dp[i-1][k][1] 初始化为负无穷，原因在于这代表在第一天之前（即还未开始交易之前）持有股票的情况。这种情况实际上是不可能的，因为在交易开始前你无法持有股票。将其设为负无穷大是一种标准的做法，用以表示这种状态的非法或不合理性，确保任何试图从这个状态得到利润的尝试都会被视作无效，从而在状态转移时不会被考虑。

在状态转移阶段，dp[i][k][0] 和 dp[i][k][1] 的更新逻辑反映了从前一天的状态到当前天的最大利润的变化。对于 dp[i][k][0]，它表示在第 i 天结束时，完成 k 次交易且不持有股票的最大利润。这可以从两个可能的前一天状态得到：一是第 i-1 天也不持有股票(dp[i-1][k][0])，二是第 i-1 天持有股票但在第 i 天卖出(dp[i-1][k][1] + prices[i-1])，这两种情况取最大值。对于 dp[i][k][1]，它表示在第 i 天结束时，完成 k 次交易且持有股票的最大利润。这同样可以从两个状态转移来：一是第 i-1 天已持有股票(dp[i-1][k][1])，二是第 i-1 天完成了 k-1 次交易且在第 i 天买入股票(dp[i-1][k-1][0] - prices[i-1])。这两个方程共同确保了在给定的交易次数和股票持有状态下，可以获得的最大利润。