买入和卖出股票的最大利润是k次

债券在每一天的成本是prices，长度为n，我需要通过买入和卖出来获得最大利润k交易（买入和卖出，不是在同一天，但我可以在同一天卖出然后再买入）。买入和卖出股票的最大利润是k次

我试过（蟒蛇）：

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。

如何解决？

来源

2017-06-19 po1son

您还可以提供一个输入和输出的例子，以便我可以处理它 – zenwraight

@zenwraight在代码示例中有'prices = [3，1，10]'，我写了什么，当你打电话给它时与'k = 2' – po1son

当然，最大利润* *是通过在'1'买入和在'10'卖出并且应该是'9'来做出的？或者有什么你不告诉我们的？ –

如果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，你不必担心溢出问题。

来源

2017-06-19 16:18:28

买入和卖出股票的最大利润是k次

回答

相关问题