Very detailed explanation and easy to understand solution. O(n) time and O(1) space. Python

• ``````import sys
class Solution(object):
def maxProfit(self, prices):
# Okay so I got this ingenious solution from EPI
# Ideally to solve this problem we should split the array into two : A[0:j-1] and A[j:] (inclusive)
# We need to find the maximum profit we can make from A[0:j-1] (inclusive)
# And the maximum profit we can make from A[j:] (inclusive)
# for every possible j and then sum both of them
# At first this seems like an O(n^2) algorithm but it can be done in O(n) two passes

# First let's compute before where index j represents the max profit we can make by day j
minPrice = sys.maxint; maxProfit = 0
before = []
for price in prices :
minPrice = min(minPrice, price)
maxProfit = max(maxProfit, price - minPrice)
before.append(maxProfit)

# Then let's compute after where index j represents the max profit we can make after day j
maxPrice = -sys.maxint -1; maxProfit = 0
after = []
for price in reversed(prices) :
maxPrice = max(maxPrice, price)
maxProfit = max(maxProfit, maxPrice - price)
after.append(maxProfit)
after.reverse()

# Then let's sum all before[j-1] representing A[0:j-1] and after[j] representing A[j:]
# special case : before[-1] is obviously zero as there is no max profit before day 0
maxProfit = 0
for j in range(len(prices)) :
if j == 0 : maxProfit = after[j]
else : maxProfit = max(maxProfit, after[j] + before[j-1])
return maxProfit

``````

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