如何修改算法或处理交易列表以获取最大利润对应的交易明细？

我们需要解决经典的最多k次股票交易最大利润问题，不仅要计算最大利润值，还要输出产生该利润的具体买卖价格对列表。例如，当价格列表为[1, 5, 2, 3, 7, 6, 4, 5]、允许3次交易时，最大利润为10，对应的交易明细应为[(1, 5), (2, 7), (4, 5)]。

现有动态规划函数已能计算最大利润，并通过全局变量保存了利润矩阵和交易矩阵，但缺少回溯交易明细的逻辑。

现有函数分析 #

原函数通过动态规划构建profit[i][j]（表示前j天最多i次交易的最大利润）和transactions[i][j]（表示达到profit[i][j]时最后一笔交易的买卖价格对），但仅返回利润值，未提取交易明细。

原代码：

profit_list = []
transaction_list = []

def findMaxProfit(price, k):
    global profit_list
    global transaction_list
    n = len(price)
    if n <= 1:
        return 0
    profit = [[0 for x in range(n)] for y in range(k + 1)]
    transactions = [[(0,0) for x in range(n)] for y in range(k + 1)]
 
    for i in range(k + 1):
        for j in range(n):
            if i == 0 or j == 0:
                profit[i][j] = 0
            else:
                max_so_far = 0
                for x in range(j): 
                    curr_price = price[j] - price[x] + profit[i-1][x]
                    if max_so_far < curr_price:
                        max_so_far = curr_price
                        transactions[i][j] = (price[x],price[j])
        
                profit[i][j] = max(profit[i][j-1], max_so_far)
                             
    profit_list = profit
    transaction_list = transactions
              
    return profit[k][n-1]

交易明细回溯方法 #

要从profit和transactions矩阵中提取交易明细，需从终点(i=k, j=n-1)反向回溯：

1. 若profit[i][j] == profit[i][j-1]，说明第j天未进行交易，直接将j减1继续回溯。
2. 若profit[i][j] > profit[i][j-1]，说明第j天完成了一笔有效交易，即transactions[i][j]对应的买卖对，将其加入结果列表。
3. 找到该交易买入价对应的天数x（即价格列表中买入价在j之前的索引），将i减1（剩余交易次数减少一次），j设为x，继续回溯。
4. 当i=0或j=0时停止回溯，最后将结果列表反转得到正序的交易明细。

修改后的完整代码 #

我们去掉全局变量，添加回溯逻辑，让函数同时返回最大利润和交易明细：

def get_transactions(price, profit_matrix, transaction_matrix, k, n):
    transactions = []
    i, j = k, n - 1
    while i > 0 and j > 0:
        # 判断当前天是否有有效交易
        if profit_matrix[i][j] > profit_matrix[i][j-1]:
            buy, sell = transaction_matrix[i][j]
            transactions.append((buy, sell))
            # 找到买入价对应的天数（j之前的位置）
            x = price.index(buy, 0, j)
            i -= 1
            j = x
        else:
            j -= 1
    # 反转得到正序交易
    return transactions[::-1]

def findMaxProfitWithTransactions(price, k):
    n = len(price)
    if n <= 1:
        return 0, []
    # 初始化利润矩阵和交易矩阵
    profit = [[0 for _ in range(n)] for _ in range(k + 1)]
    transactions = [[(0, 0) for _ in range(n)] for _ in range(k + 1)]
 
    for i in range(k + 1):
        for j in range(n):
            if i == 0 or j == 0:
                profit[i][j] = 0
            else:
                max_so_far = 0
                for x in range(j): 
                    curr_profit = price[j] - price[x] + profit[i-1][x]
                    if max_so_far < curr_profit:
                        max_so_far = curr_profit
                        transactions[i][j] = (price[x], price[j])
                # 取前一天的利润或当前最大利润
                profit[i][j] = max(profit[i][j-1], max_so_far)
    
    max_profit = profit[k][n-1]
    transaction_details = get_transactions(price, profit, transactions, k, n)
    return max_profit, transaction_details

# 测试示例
prices = [1, 5, 2, 3, 7, 6, 4, 5]
k = 3
max_p, trans = findMaxProfitWithTransactions(prices, k)
print(f"最大利润：{max_p}")
print(f"交易明细：{trans}")

运行结果：

最大利润：10
交易明细：[(1, 5), (2, 7), (4, 5)]

注意事项 #

• 若价格列表中存在重复价格，price.index(buy, 0, j)会返回第一个匹配的索引，这符合原动态规划逻辑中x的遍历顺序（从0到j-1取第一个最优解）。
• 原交易矩阵中可能存在买入价大于卖出价的无效交易对，但回溯时通过profit[i][j] > profit[i][j-1]的判断会自动跳过这些无效项，因为这类交易不会带来利润提升。

内容的提问来源于stack exchange，提问作者CTowers99