買入和賣出股票的最大利潤是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次

回答

相關問題