Best Time to buy and sell stock III

Question

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Thoughts

两次交易之间有一个分界点，对每一个分界点，计算左右两边的最大profit

在这个过程中有很多的重复计算，会exceed time limit,可以使用dp来减少运算量

先从左往右一遍找到从左边到第i个的最大profit 再从右往左一遍找到从i个到右边的最大profit 然后就可以用这些dp得到的数据直接计算

Solution

class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    def maxProfit(self, prices):
        if not prices:
            return 0
        length = len(prices)

        #from left to i
        left = [ 0 for i in range(length)]
        minPrice = prices[0]
        for i in range(1, length):
            if prices[i] <  minPrice:
                minPrice = prices[i]
            left[i] = max(left[i-1], prices[i] - minPrice)

        #from i to from
        right = [ 0 for i in range(length)]
        maxPrice = prices[length - 1]
        for i in range(length-2, -1, -1):
            if prices[i] > maxPrice:
                maxPrice = prices[i]
            right[i] = max(right[i+1], maxPrice - prices[i])

        #start calcuate for each index
        maxProfit = 0
        for i in range(length):
            profit = left[i] + right[i]
            if profit > maxProfit:
                maxProfit = profit
        return maxProfit