返回利润最大的特定K笔交易

Question

这是从一个价格列表通过k次交易返回最大利润的问题衍生出来的一道题。我不仅想返回利润，还想返回一个包含产生最大利润的交易的列表。例如，如果价格列表是 [1, 5, 2, 3, 7, 6, 4, 5] 并且允许的 k 次交易是 k，最大利润是 10，但我想返回一个列表像 [(1, 5), (2, 7), (4, 5)]，其中第一个值是买入价，第二个值是卖出价。

我有以下函数，在函数之外还有两个变量，我在函数内部设置为全局变量，以便返回可能的利润和交易的完整列表

profit_list = []
transaction_list = []

def findMaxProfit(price, k):
    global profit_list
    global transaction_list
    # get the number of days `n`
    n = len(price)
    # base case
    if n <= 1:
        return 0
    # profit[i][j] stores the maximum profit gained by doing
    # at most `i` transactions till j'th day
    profit = [[0 for x in range(n)] for y in range(k + 1)]
    # transactions[i][j] stores the buying price and sell price
    transactions = [[(0,0) for x in range(n)] for y in range(k + 1)]
 
    # fill profit[][] in a bottom-up fashion
    for i in range(k + 1):
        for j in range(n):
            # profit is 0 when
            # i = 0, i.e., for 0th day
            # j = 0, i.e., no transaction is being performed
            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]

例如，如果 prices = [1, 5, 2, 3, 7, 6, 4, 5] 且 k = 3，则该函数会返回最大利润（在本例中为 10）和给定可能的交易transaction_list 变量如下

[[(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],
 [(0, 0), (1, 5), (1, 2), (1, 3), (1, 7), (1, 6), (1, 4), (1, 5)],
 [(0, 0), (1, 5), (1, 2), (2, 3), (2, 7), (2, 6), (2, 4), (2, 5)],
 [(0, 0), (1, 5), (1, 2), (2, 3), (2, 7), (2, 6), (6, 4), (4, 5)]]

为了获得最大利润的交易列表，我可以对交易列表的功能或操作进行哪些更改？