Best Time to Buy and Sell Stock IV

Problem: Best Time to Buy and Sell Stock IV

Maximum profit at time T with K transactions is decided by selling at time T with K transaction and not sell which means maximum profit at time T-1 with K transaction. Profit by selling at time T with K transactions is decided by sell at T-1 with K transaction plus the recent price difference (which means swapping the recent selling) and global maximum profit at T-1 with K-1 transaction.

Code in Python:

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if k == 0: return 0
        n = len(prices)
        if k >= n / 2:
            profit = 0
            for i in xrange(1, n):
                if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1]
            return profit
        sell = [[0] * (k+1) for _ in xrange(n)]
        dp = [[0] * (k+1) for _ in xrange(n)]

        for i in xrange(1, n):
            profit = prices[i] - prices[i-1]
            for j in xrange(1, k+1):
                sell[i][j] = max(dp[i-1][j-1] + profit, sell[i-1][j] + profit)
                dp[i][j] = max(dp[i-1][j], sell[i][j])
        return dp[-1][-1]