Stupid DP. Python solution

  • -1
        def maxProfit(self, prices):
        ##DP: if not sell on day n, we have D(n) = D(n-1)
        ##    if sell on day n(bought at day k), we have D(n) = prices[n] - prices[k] + D(k-2).
        ##    D(k-1) can't buy since we bought at day k, D(k-1) also can't sell otherwise cooldown on day k.
        ##    D(n) = max{D(n-1),prices[n] - prices[k] + D(k-2)}
        length = len(prices)
        if length == 0:
            return 0
        D = [0]*length
        max_val = -1
        for i in range(length):
            if prices[i] > prices[i-1]:##if prices[i] is lower, just leave it
                maximal = -1
                for k in range(i+1):
                    index = i-k
                    if prices[index] > prices[i]:##stop, no need to go down
                    if index-2>=0:
                        temp = max(D[i-1],prices[i]-prices[index] + D[index-2])
                        if temp > maximal:
                            maximal = temp
                        temp = max(D[i-1], prices[i]-prices[index])
                        if temp > maximal:
                            maximal = temp
                D[i] = maximal
                D[i] = D[i-1]
        return D[length-1]

Log in to reply

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