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

  • 0
    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)
            # 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)
            # 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.