买卖股票的最佳时机 III

难度:

标签:

题目描述

给定一个数组，它的第 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⁵

代码结果

运行时间: 2012 ms, 内存: 59.9 MB

// Java solution with Streams (conceptual)
// Note: Java Streams are not ideal for this type of problem as it involves state and multiple passes over the data.
// However, we can use them to some extent for cleaner code.
 
import java.util.stream.IntStream;
 
public class MaxProfitStream {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int n = prices.length;
        int[] buy = new int[n];
        int[] sell = new int[n];
        int[] buy2 = new int[n];
        int[] sell2 = new int[n];
        
        buy[0] = -prices[0];
        sell[0] = 0;
        buy2[0] = -prices[0];
        sell2[0] = 0;
        
        IntStream.range(1, n).forEach(i -> {
            buy[i] = Math.max(buy[i-1], -prices[i]);
            sell[i] = Math.max(sell[i-1], buy[i-1] + prices[i]);
            buy2[i] = Math.max(buy2[i-1], sell[i-1] - prices[i]);
            sell2[i] = Math.max(sell2[i-1], buy2[i-1] + prices[i]);
        });
        return sell2[n-1];
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在动态规划解法中，为什么选择使用三维数组dp[i][k][0]和dp[i][k][1]来表示状态？两个维度分别代表什么含义？

▷

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

🦆

解题中提到的基础情况（base case）设置是如何考虑的，尤其是dp[i-1][k][1]初始化为负无穷的原因是什么？

▷

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

🦆

在进行状态转移时，dp[i][k][0]和dp[i][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])。这两个方程共同确保了在给定的交易次数和股票持有状态下，可以获得的最大利润。

相关问题