通过买卖股票获得最大利润正好是k倍

Question

每天债券的成本以长度为prices的数组n给出，我需要找到我可以通过在交易中买卖（按顺序买卖）所能获得的最大利润。不是在同一天。但我可以在同一天卖出然后买入）。在

我试过（Python）：

prices = [3, 1, 10]
n = len(prices)

def aux(i, j):
    if j == n - 1 or i == 0:
        return 0
    s = [(prices[j + t] - prices[j]) + aux(i - 1, j + t)
         for t in range(1, n - j)]
    return max(aux(i, j + 1), max(s)) if s else aux(i, j + 1)

def max_profit(k):
    return aux(k, 0)

但是对于代码中给定的数组，使用k=2我得到9，而它应该是(1 - 3) + (10 - 1) = 7。它似乎在最多k笔交易中获得最大利润，而不完全是k笔交易

怎么能修好？在

Answer 1

如果k未完全使用，则停止条件不应允许函数成功完成。试试这个

if i == 0:
    return 0
elif j == n - 1:
    return -2**30

在第一种情况下，当i == 0时，这意味着k被完全消耗了，我们不能继续下去了。所以我们不能再赢或输了，所以返回0。在

现在，在第二个条件下，假设第一个条件不是真的，这意味着我们到达数组的末尾时没有完全消耗k。因此，这不是一个有效的答案。要将一个答案标记为无效，我们必须给它一个非常坏的值，以便与任何其他有效答案相比，它无论如何都会被拒绝。在

因为这是一个最大化问题，一个坏值意味着一个非常小的数字，所以当我们用其他答案最大化时，它总是被丢弃。在

-2**30是一个非常接近整数最小值的值，所以这个值应该足够小。我假设您的所有操作都适合一个32位整数，因此这个值应该足够小。如果这不是真的，你必须选择一个小的值，足够小的值，你可以在一个有效的答案中得到的最小值。您可以选择-2**60甚至-2**100，因为这是Python，您不必担心溢出问题。在