123. Best Time to Buy and Sell Stock III

AC的答案，基本的思想是，找出一個transaction在一個index之前完成可以獲得的最大值，然后再找出，一個transaction在一個index之后完成可獲得的最大值，只要找到這個index就可以了。但是這樣做并不是DP，如果要解決at most k transaction好像這樣就不行了。那道題在188，估計下周末能夠做到。到時候再說。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
        profit_from_left = [0 for _ in range(len(prices))]
        profit_from_right = profit_from_left[:]

        cur_min = prices[0]
        for i in range(1, len(prices)):
            profit_from_left[i] = max(0, prices[i] - cur_min, profit_from_left[i-1])
            cur_min = min(cur_min, prices[i])
                
        cur_max = prices[-1]
        for i in range(len(prices)-1)[::-1]:
            profit_from_right[i] = max(0, cur_max - prices[i], profit_from_right[i+1])
            cur_max = max(cur_max, prices[i])
        
        # print profit_from_left
        # print profit_from_right
        max_profit = 0
        for index in range(len(prices)):
            max_profit = max(profit_from_left[index]+profit_from_right[index], max_profit)
        return max_profit