我们正向扫一遍, 求出每天的maxProfit放到maxProfitForward里, 再逆向扫一遍, 求出每天的maxProfit放到maxProfitBackward里, 都是O(N)时间。如果不进行transaction, maxProfit为0。如果只进行一次transaction, maxProfit为maxProfitForward[-1]。如果进行两次transaction, 顺序只能是买入->卖出->买入->卖出, 设第一次卖出发生在前i天, 第二次卖出发生在第i+1天到最后一天之间, 那么maxProfit就是 maxProfitForward[i-1] + maxProfitBackward[i] 的最大值, 还是O(N)时间。总的时间复杂度是O(N)。

First we scan forward and put everyday's maxProfit into maxProfitForward list, then we scan backward and put everyday's minProfit into maxProfitBackward list. Time complexity is O(N). If there's no transaction, the maxProfit will be 0. If there's only one transaction, the maxProfit will be maxProfitForward[-1]. If there are two transactions, the order must be buying -> selling -> buying -> selling. We assume that the first selling happens within first i days and the second selling happens between i+1 day and the last day, so maxProfit is the max value of ( maxProfitForward[i-1] + maxProfitBackward[i] ). Time complexity is O(N). The total time complexity is O(N).

class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        length = len(prices)
        if length == 0: return 0
        
        maxProfitForward = []
        minPrice = prices[0]
        maxProfit = -1
        for currPrice in prices:
            minPrice = min(minPrice, currPrice)
            maxProfit = max(maxProfit, currPrice - minPrice)
            maxProfitForward.append(maxProfit)
        
        maxProfitBackward = []
        maxPrice = prices[-1]
        maxProfit  = -1
        for currPrice in reversed(prices):
            maxPrice = max(maxPrice, currPrice)
            maxProfit = max(maxProfit, maxPrice - currPrice)
            maxProfitBackward.insert(0, maxProfit)
        
        maxProfit = maxProfitForward[-1] # 0 or 1 transaction
        for i in xrange(length - 1): # 2 transactions
            maxProfit = max(maxProfit, maxProfitForward[i] + maxProfitBackward[i + 1])
        return maxProfit