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


  • 0
    L
    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
            
            
    

Log in to reply
 

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