Very simple O(n) dynamic programming solution


  • 0
    O

    Define STATE f(i) as the maximum profit we can get at day i.

    Then we have two scenarios for each day, we sell here or not:
    f(i) = max(f(i - 1), max(f(j - 2) + prices[i] - prices[j]))
    = max(f(i - 1), prices[i] + max(f(j - 2) - prices[j])), j = 0, 1, ..., i - 1
    , where j is the last day we buy the stock.

    Then we just keep track of the maximum value of diff = f(j -2), prices[j].
    code:

        def maxProfitDP(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            f = [0] * (len(prices) + 1) # pad leading zero to neutralize empty list case
            diff = float('-inf') # f(j - 1) - prices[j]
            for i in range(1, len(prices) + 1):
                f[i] = max(f[i - 1], prices[i - 1] + diff)
                diff = max(diff, f[max(0, i - 2)] - prices[i - 1])
            return f[len(prices)]
    

Log in to reply
 

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