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

• 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

• 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).

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