Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

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

Example

Given an example [4,4,6,1,1,4,2,5], return 6.

Solution

Subarray 对比， 求I后的最大值的时候，这道题股票的买卖是有顺序的，但是Subarray是有范围的从后到前的写法不变。

分析：动态规划法。以第i天为分界线，计算第i天之前进行一次交易的最大收益preProfit[i]，和第i天之后进行一次交易的最大收益postProfit[i]，最后遍历一遍，max{preProfit[i] + postProfit[i]} (0≤i≤n-1)就是最大收益。第i天之前和第i天之后进行一次的最大收益求法同Best Time to Buy and Sell Stock I。

分割线算法

2 4 5 1 2 4 6

left

0 2 3 3 3 3 5

r 5 5 5 5 4 2 0

prices[0:n-1] => prices[0:i] + prices[i:n-1]

左边扫描一次，得到p[n] , 第N天的最大效益，

对于这个特定分割来说，最大收益为两段的最大收益之和。每一段的最大收益当然可以用I的解法来做。而III的解一定是对所有0<=i<=n-1的分割的最大收益中取一个最大值。为了增加计算效率，考虑采用dp来做bookkeeping。目标是对每个坐标i：

计算A[0:i]的收益最大值：用minPrice记录i左边的最低价格，用maxLeftProfit记录左侧最大收益

计算A[i:n-1]的收益最大值：用maxPrices记录i右边的最高价格，用maxRightProfit记录右侧最大收益。

最后这两个收益之和便是以i为分割的最大收益。将序列从左向右扫一遍可以获取1，从右向左扫一遍可以获取2。相加后取最大值即为答案。

class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    def maxProfit(self, prices):
        # write your code here
        total = 0
        n = len(prices)

        if n <= 1:
            return 0

        p1 = [0] * n
        p2 = [0] * n

        low = sys.maxint
        total = 0
        high = prices[-1]

        for i in range(n):
            low = min(low, prices[i])
            total = max(total, prices[i] - low)
            p1[i] = total

        for i in range(n-2, -1, -1):
            high = max(high, prices[i])
            p2[i] = max(p2[i + 1], high - prices[i])

        for i in range(n):
            total = max(total, p1[i] + p2[i])
        return total