# 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://liuxue2010.gitbook.io/data-structure-and-algorithms/array-and-numbers/best-time-to-buy-and-sell-stock-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.