通过恰好k次买卖股票获得最大利润 [英] Maximum profit by buying and selling a share exactly k times

问题描述

每天的债券成本在长度为n的数组prices中给出，我需要找到可以通过精确地买入和卖出的最大利润k交易(以该顺序买卖.不在同一天.但是我可以在同一天卖出然后买入).

The cost of a bond on each day is given in array prices of length n, and I need to find the maximum profit that I can make by buying and selling in exactly k transactions (buying and selling, in that order. not in the same day. but I can sell and then buy in the same day).

我尝试过(Python):

I tried (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时应该得到(1 - 3) + (10 - 1) = 7时得到9.它似乎在最多k笔交易中获得了最大的利润，而并非恰好是k笔.

But for the given array in the code, and with k=2 I get 9 when It should be (1 - 3) + (10 - 1) = 7. It seem to get the maximum profit for at most k transactions and not exactly k.

如何解决?

推荐答案

如果k未被完全使用，则您的停止条件不应使函数成功完成.尝试这样的事情

Your stopping condition shouldn't allow the function to finish successfully if k is not totally consumed. Try something like this

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

在第一种情况下，当i == 0时，这意味着k被完全消耗掉了，我们无法继续进行.这样我们就不能再输了，因此返回0.

In the first case, when i == 0, that means that k is totally consumed and we can't proceed anymore. so we can't win or lose anymore, thus return 0.

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

Now, in the second condition, assuming that the first one wasn't true, that means that we reached the end of the array without totally consuming k. Hence, this is not a valid answer. To mark an answer as invalid, we have to give it a really bad value so it would be rejected anyway compared to any other valid answer.

由于这是一个最大化问题，所以差的值表示一个很小的数字，因此当我们用其他答案最大化时，它将始终被丢弃.

Since this is a maximization problem, a bad value means a very small number, so when we maximize with other answers, it'll always be discarded.

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

-2**30 is a pretty close value to the minimum value of an integer, so this should be small enough. I'm making the assumption that all your operations will fit in a 32-bit integer, hence this should be a small enough value. If this is not true you have to pick a small value, enough to be less that the smallest value that you could ever get in a valid answer. You can pick -2**60 or even -2**100 since this is Python and you don't have to worry about overflow issues.

这篇关于通过恰好k次买卖股票获得最大利润的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！