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
Very detailed explanation and easy to understand solution. O(n) time and O(1) space. Python
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.