# Short python solution, O(n) runtime, O(1) space

• The question is simple. You want to find the difference of the maximum and the minimum. The only trick is that the bigger number should come after the smaller number.

So, here is how I tackled it. Instead of going forward, I scanned through the list of prices backward to store the current maximum number. Update the biggest difference along the way.

``````class Solution:
# @param prices, a list of integer
# @return an integer
def maxProfit(self, prices):
length = len(prices)
if length==0:
return 0
temp = prices[length-1]
res = 0
for i in range(length-1,-1,-1):
temp = max(temp,prices[i])
if temp - prices[i] > res:
res = temp - prices[i]
return res``````

• ``````class Solution:
# @param prices, a list of integer
# @return an integer
def maxProfit(self, prices):
if len(prices) == 0:
return 0
minPrice = prices[0]
maxProfit = 0
for i in range(0, len(prices)):
if prices[i] < minPrice:
minPrice = prices[i]
if prices[i] - minPrice > maxProfit:
maxProfit = prices[i] - minPrice
return maxProfit``````

• ``````def maxProfit(self, prices):
if len(prices) < 1:
return prices
if len(prices) > 1:
profit = []
for i in range(1,len(prices)):
for j in range(0,i):
profit.append(prices[i]-prices[j])
return max(profit)
``````

I did in a pretty similar way, but i got an error saying memory limit exceeded. why is that?

• Very nice idea!Thank you for sharing.

• Actually, not similar.you got o(n^2) runtime,and he got o(n).The list you created is too large.

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