# Clean python code O(n) solution without dp

• ``````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``````

• 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?

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