Share Slightly Different Concise DP Approach, O(n*k), O(k) memory (beats 99%)


  • 0
    A
    class Solution(object):
        def maxProfit(self, k, prices):
            if len(prices) < 2: return  0
            if k < len(prices) / 2:
                buy = [-1e18] * (k + 1)
                sell = [0] * (k + 1)
                for price in prices:
                    for i in range(1, k + 1):
                        sell[i] = max(sell[i], buy[i] + price)
                        buy[i] = max(buy[i], sell[i - 1] - price)
                return max(sell)
            else:
                prof = 0
                for i in range(1, len(prices)):
                    if prices[i] > prices[i - 1]:
                        prof += prices[i] - prices[i - 1]
                return prof
    

    I formulated this idea based on the solution for Buy and Sell Stock III where some solutions explained a state machine. We define the following dp functions:

    buy[i][j] = Maximum profit at to buy stock at index i while making j'th buy tranxn
    sell[i][j] = Maximum profit at to buy stock at index i while making j'th sell tranxn
    

    DP equations:

    sell[i][j] = max(sell[i][j], buy[i - 1][j] + price[i])
    buy[i][j] = max(buy[i][j], sell[i][j - 1] - price[i])
    

    Since state for each j depends on only previous state (i - 1)
    For each price:

    sell[j] = max(sell[j], buy[j] + price)
    buy[j] = max(buy[j], sell[j - 1] - price)
    

    For the case k > len / 2 I follow similar approach as by the best answers to calculate maximum profit by collecting all possible increase in stock price.


Log in to reply
 

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