A simple python solution, O(2n) time, O(n) space


  • 1
    T
    class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        profit = [0]*len(prices)
        low, high = float('inf'), float('-inf')
        max_profit = res = 0
        for n, p in enumerate(prices):
            low = min(p, low)
            max_profit = max(max_profit, p-low)
            profit[n] = max_profit
        max_profit = 0
        for n, p in reversed(list(enumerate(prices))):
            high = max(p, high)
            max_profit = max(max_profit, high-p)
            res = max(res, max_profit+profit[n])
        return res
    

    scan from left, profit[n] means from 0-n day the max_profit we can get

    scan from right, profit[n] means from n-last day the max_profit we can get

    add left and right, find the result


  • 1
    H

    There is no such thing O(2n). You can count the exact loops though. Somehow, I don't like this code since it is pythonic for being pythonic. esp. reversed(list(enumerate(prices))) is horrible as you can actually do a loop on index generator with xrange (or range in python 3).


Log in to reply
 

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