Clean python code O(n) solution without dp


  • 0
    class Solution(object):
        def getProfits(self, toEnd=False):
            r, minPrice, maxPrice, profit = [], None, None, 0
            for p in (self.prices[::-1] if toEnd else self.prices):
                bigger, smaller = p > maxPrice, p < minPrice
    
                if minPrice is None or [smaller, bigger][toEnd]:
                    minPrice = maxPrice = p
                elif [bigger, smaller][toEnd]:
                    if toEnd:
                        minPrice = p
                    else:
                        maxPrice = p
                profit = max(profit, maxPrice - minPrice)
    
                r.append(profit)
            return (r[::-1] + [0]) if toEnd else r
    
        def maxProfit(self, prices):
            self.prices = prices
    
            (toStart, toEnd), profit = map(self.getProfits, (False, True)), 0
            for i in xrange(len(prices)):
                profit = max(profit, toStart[i] + toEnd[i + 1])
    
            return profit

  • 0
    J

    Your solution is:

    First, calculate two array: 1. toStart[i] = max( toStart[i-1], prices[i] - min(prices[0:i]) ), 2. toEnd[i] = max( toEnd[i-1], reversePrices[i] - min(reversePrices[0:i]) ).

    And then get max( toStart[i] + toEnd[i+1] ).

    Your thought is exactly DP, isn't it?


Log in to reply
 

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