[188. Best Time to Buy and Sell Stock IV] #leetcode

188_1015.py

class Solution(object):
  # O(n*k) O(n*k)
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        # corner case
        if not prices or k == 0:
            return 0
        
        n = len(prices)
        # became buy sell II 
        if k >= n // 2:
            profit = 0
            for i in range(1, n):
                if prices[i-1] < prices[i]:
                    profit += prices[i] - prices[i-1]
            return profit
        
        # general case
        # dp[k][i] refers to max profit util prices[i] after kth transactions
        dp = [[0 for j in range(n)] for i in range(k+1)] 
        
        for kk in range(1, k+1):
            tmp_max = -prices[0]
            for ii in range(1, n):
                dp[kk][ii] = max(dp[kk][ii-1], # do nothing in prices[ii]
                                 prices[ii] + tmp_max) # sell at prices[ii]
                tmp_max = max(tmp_max, dp[kk-1][ii-1] - prices[ii])
        
        return dp[k][n-1]