188. Best Time to Buy and Sell Stock IV

Loading...LeetCode

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        if n <= 1: return 0
        
        dp = [[0 for _ in range(n)] for _ in range(k+1)]
        
        # i: how many transaction made
        # j: # of day
        for i in range(1, k+1):
            maxDiff = -prices[0]
            for j in range(1, n):
                maxDiff = max(maxDiff, dp[i-1][j-1] - prices[j-1])
                dp[i][j] = max(dp[i][j-1], prices[j] + maxDiff)
                
        return dp[-1][-1]