题目描述

你有一个整数数组prices，其中prices[i]表示股票第i天的价格。你的任务是找到在最多完成两次交易的情况下，可以获得的最大利润。

要求：

• 每次交易必须包括买入和卖出，且必须在卖出之后才能再次买入。
• 如果无法盈利，可以选择不进行任何交易。

示例：

1. 输入：prices = [3,3,5,0,0,3,1,4]
   输出：6
   解释：
   • 第一次交易：第4天买入（价格=0），第6天卖出（价格=3），利润=3。
   • 第二次交易：第7天买入（价格=1），第8天卖出（价格=4），利润=3。
   • 总利润 = 3 + 3 = 6。
2. 输入：prices = [1,2,3,4,5]
   输出：4
   解释：
   • 第1天买入（价格=1），第5天卖出（价格=5），利润=4。
   • 无法完成第二次交易。
3. 输入：prices = [7,6,4,3,1]
   输出：0
   解释：无论如何交易，都无法获利。

---

解题思路

这是一道典型的动态规划问题。为了帮助候选人更好地理解问题并应对面试官的追问，以下是详细的解题步骤和场景分析。

---

思路分解

1. 问题分为两部分：
   • 第一阶段：找到在每一天之前最多完成一次交易的最大利润。
   • 第二阶段：找到在每一天之后最多完成一次交易的最大利润。
   • 最后将两部分利润相加，取最大值。
2. 动态规划设计：
   • 使用递归+记忆化（memoization）来解决问题。
   • 状态表示：
     • i：当前天数。
     • t：已完成的交易次数（0、1或2）。
     • can_buy：是否可以进行买操作（1表示可以买，0表示可以卖）。
   • 状态转移：
     • 如果可以买：
       • 跳过当前天：profit = dfs(i+1, t, can_buy)
       • 买入股票：profit = -prices[i] + dfs(i+1, t, 0)
     • 如果可以卖：
       • 跳过当前天：profit = dfs(i+1, t, can_buy)
       • 卖出股票：profit = prices[i] + dfs(i+1, t+1, 1)
3. 基础条件：
   • 当天数i超出范围，或完成两次交易t == 2时，利润为0。

---

代码实现

        
def maxProfit(prices):
    n = len(prices)
    memo = {}

    def dfs(day, transactions, can_buy):
        # 如果到最后一天或者交易已完成两次，利润为0
        if day == n or transactions == 2:
            return 0
        # 如果当前状态已计算过，直接返回
        if (day, transactions, can_buy) in memo:
            return memo[(day, transactions, can_buy)]

        # 当前状态的最大利润，初始化为跳过当前天
        profit = dfs(day + 1, transactions, can_buy)

        if can_buy:
            # 可以买：选择买入或跳过
            profit = max(profit, -prices[day] + dfs(day + 1, transactions, 0))
        else:
            # 可以卖：选择卖出或跳过
            profit = max(profit, prices[day] + dfs(day + 1, transactions + 1, 1))

        # 记录当前状态的最大利润
        memo[(day, transactions, can_buy)] = profit
        return profit

    return dfs(0, 0, 1)

        
    

---

面试场景还原

面试官问题1：
“能否描述你是如何划分问题的？”

• 候选人回答：“我将问题分为两个阶段：第一阶段是在某一天之前找到最大利润，第二阶段是在某一天之后找到最大利润。通过动态规划，我可以合并这两个阶段的结果。”

面试官追问1：
“如果交易次数不限，该如何扩展？”

• 候选人回答：“我们可以将状态中的交易次数从固定的2次扩展为k次，增加一个维度来记录。这样，时间复杂度会从O(n)变为O(nk)。”

面试官问题2：
“如何优化空间复杂度？”

• 候选人回答：“可以通过滚动数组优化空间，将三维数组的空间复杂度从O(n*2*3)优化到O(2*3)，只需保留上一天的状态。”

面试官追问2：
“能否解释递归的时间复杂度？”

• 候选人回答：“递归中每个状态仅被计算一次，因此时间复杂度为O(n)，因为我们总共有n*2*3个状态。”

---

示例分析

1. 输入：prices = [3,3,5,0,0,3,1,4]
   • 第1天：跳过。
   • 第4天：买入，利润 = -0。
   • 第6天：卖出，利润 = 3。
   • 第7天：买入，利润 = -1。
   • 第8天：卖出，利润 = 4。
     总利润 = 3 + 3 = 6
2. 输入：prices = [1,2,3,4,5]
   • 第1天买入，第5天卖出，利润=4。
3. 输入：prices = [7,6,4,3,1]
   • 无论如何操作，都无法盈利。

---

CSOAhelp的作用

通过CSOAhelp的详细注释和模拟问题分解，候选人可以：

1. 更加清晰地理解递归和动态规划的本质。
2. 在面试中从容应对面试官的复杂追问。
3. 通过提供的模板代码和面试问题引导，快速进入答题状态。
   选择CSOAhelp，轻松搞定算法面试！

经过csoahelp的面试辅助，候选人获取了良好的面试表现。如果您需要面试辅助或面试代面服务，帮助您进入梦想中的大厂，请随时联系我。

If you need more interview support or interview proxy practice, feel free to contact us. We offer comprehensive interview support services to help you successfully land a job at your dream company.