Python: A very easy solution based on the previous solution. We only need to calculate 3 additional profits and choose the best as the 2nd transaction.


  • 0

    There are at most 2 transactions:

    1. The one that we calculated in the previous problem, which is the biggest profit. We call it "profit1" and its range is [a,b] (a,b are indices of the left bound and right bound).
    2. How can we find the 2nd transaction? We only need to consider the following 3 cases:
      a. We calculate the biggest profit in prices[:a] (before profit1)
      b. We calculate the biggest profit in prices[b+1:] (after profit1)
      c. We calculate the biggest price retreat in prices[a:b+1] (inside profit1), which is equivalent to the calculation of biggest profit in prices[a:b+1][::-1] (reversed profit1)

    Code is as follows:

    class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            # we need the best profit and its range in prices (the 1st transaction)
            profit1, l, r = self.maxProfit_1(prices)
            
            # then we consider other cases where we can make the additional profit (the 2nd transaction)
            profits=[]
            # we calculate the profit right of the range of "profit1"
            profits.append(self.maxProfit_1(prices[r:]))
            # we calculate the profit left of the range of "profit1"
            profits.append(self.maxProfit_1(prices[:l]))
            # we calculate the maximum price retreat(short trade) inside the range of "profit1"
            profits.append(self.maxProfit_1(prices[l:r+1][::-1]))
            # we choose the biggest among "profits" as the 2nd transaction
            profit2=max([profit[0] for profit in profits])
            
            return profit1+profit2
    
        def maxProfit_1(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            # we just need to do a little modification of the last solution
            # we use mstart and mend to record the index of the best profit
            mstart, bi, b, mend, m = 0, 0, prices[0] if prices else 0, 0, 0
            for i,x in enumerate(prices):
                if x<b:
                    b=x
                    bi=i
                if x>b:
                    if x-b>m:
                        m=x-b
                        mstart=bi
                        mend=i
            return m,mstart, mend

Log in to reply
 

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