债券每天的成本在长度为 n
的数组 prices
中给出,我需要找到通过买卖可以获得的最大利润在恰好 k
笔交易中(买卖,按照那个顺序。不是在同一天。但我可以在同一天卖出然后买入)。
我试过(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。
如何修复?
最佳答案
如果 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,您不必担心溢出问题。
关于python - 通过恰好 k 次买卖股票获得最大利润,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44634395/