Участник:Froyg/ ds

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/submissions/

 
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if k <= 0 or len(prices) < 2:
            return 0
        if k > len(prices) // 2:
            result = 0
            for i in range(len(prices)):
                result += max(prices[i] - (prices[i - 1] if i > 0 else prices[i]), 0)
            return result
        else:
            buy = [float('-inf')] * k
            sell = [0] * k
            for i in range(len(prices)):
                    for j in range(k):
                        buy[j] = max(buy[j],(sell[j - 1] if j > 0 else 0 ) - prices[i])
                        sell[j] = max(sell[j],buy[j] + prices[i])
        return sell[-1]