There are at most 2 transactions:
- 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).
- 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 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 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