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

  • 0

    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

    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.