python solution, O(KN) in time, O(N) in space


  • 0
    M

    it beats 90% in python, it inpired by @weijiac.

    def maxProfit(self, k, prices):
        if k <= 0 or len(prices) < 2: return 0
        max_profit, length = 0, len(prices)
        if k >= length//2:
            for i in xrange(1,length):
                max_profit += max(prices[i]-prices[i-1],0)
            return max_profit
            
        release = [0]*k
        hold = [float('-inf')]*k
        for i in prices:
            for j in range(k-1, 0, -1):
                release[j] = max(release[j], hold[j] + i)
                hold[j] = max(hold[j], release[j-1] - i)
            release[0] = max(release[0], hold[0] + i)
            hold[0] = max(hold[0], -i)
        return release[-1]
    

  • 0
    S

    a little explanation of what is hold, what is release would help


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.