> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/high_frequency/best_time_to_buy_and_sell_stock_iii.md).

# Best Time to Buy and Sell Stock III

## Question

<https://leetcode.com/problems/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.

## Analysis

**一种算法比较容易想到：**\
找寻一个点j，将原来的prices\[0..n-1]分割为prices\[0..j]和prices\[j..n-1]，分别求两段的最大profit。\
内层循环与Best Time to Buy and Sell Stock相同，为O(n), 外层循环为O(n)，记录不同的j两段maxProfit的值需要O(n)空间，因此总体时间复杂度为O(n^2)，空间复杂度为O(n)。

**改进（参考pickless的讲解）:**\
对于点j+1，求prices\[0..j+1]的最大profit时，很多工作是重复的，在求prices\[0..j]的maxProfit中已经计算过了。\
类似于Best Time to Buy and Sell Stock，可以在O(1)的时间从prices\[0..j]推出prices\[0..j+1]的最大profit。\
但是如何从prices\[j..n-1]推出prices\[j+1..n-1]？反过来思考，我们可以用O(1)的时间由prices\[j+1..n-1]推出prices\[j..n-1]。\
最终算法：\
数组l\[i]记录了prices\[0..i]的最大profit，\
数组r\[i]记录了prices\[i..n]的最大profit。\
已知l\[i]，求l\[i+1]是简单的，同样已知r\[i]，求r\[i-1]也很容易。\
最后，我们再用O(n)的时间找出最大的l\[i]+r\[i]，即为题目所求。\
这样时间复杂度O(n), 空间复杂度O(n)

参考 <http://blog.csdn.net/fightforyourdream/article/details/14503469>

**状态机State Machine：**

[https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/149383/Easy-DP-solution-using-state-machine-O(n)-time-complexity-O(1)-space-complexity](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/149383/Easy-DP-solution-using-state-machine-O%28n%29-time-complexity-O%281%29-space-complexity)

这种想法很神奇：

```
// Assume we are in state S
// If we buy, we are spending money but we can also choose to do nothing
// Doing nothing means going from S->S
// Buying means going from some state X->S, losing some money in the process
S = max(S, X-prices[i])

// Similarly, for selling a stock
S = max(S, X+prices[i])
```

Java Implementation

```java
public class Solution {
    int maxProfit(int[] prices) {
    if(prices == null || prices.length == 0) return 0;
    int s1=-prices[0], s2=Integer.MIN_VALUE,s3=Integer.MIN_VALUE,s4=Integer.MIN_VALUE;

    for(int i=1;i<prices.length;++i) {            
        s1 = Math.max(s1, -prices[i]);
        s2 = Math.max(s2, s1+prices[i]);
        s3 = Math.max(s3, s2-prices[i]);
        s4 = Math.max(s4, s3+prices[i]);
    }
    return Math.max(0,s4);
    }
}
```

## Solution

A Intuitive Implementation Using Divide And Conquer

```java
import java.util.*;

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // find maxProfit for {0, j}, find maxProfit for {j + 1, n - 1}
        // find max for {max{0, j}, max{j + 1, n - 1}}

        if (prices == null || prices.length == 0) {
            return 0;
        }

        int maximumProfit = 0;
        int n = prices.length;

        ArrayList<Profit> preMaxProfit = new ArrayList<Profit>(n);
        ArrayList<Profit> postMaxProfit = new ArrayList<Profit>(n);
        for (int i = 0; i < n; i++) {
            preMaxProfit.add(maxProfitHelper(prices, 0, i));
            postMaxProfit.add(maxProfitHelper(prices, i + 1, n - 1));
        }
        for (int i = 0; i < n; i++) {
            int profit = preMaxProfit.get(i).maxProfit + postMaxProfit.get(i).maxProfit;
            maximumProfit = Math.max(profit, maximumProfit);
        }
        return maximumProfit;
    }

    private Profit maxProfitHelper(int[] prices, int startIndex, int endIndex) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int i = startIndex; i <= endIndex; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
            if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return new Profit(maxProfit, minPrice);
    }

    public static void main(String[] args) {
        int[] prices = new int[]{4,4,6,1,1,4,2,5};
        Solution s = new Solution();
        System.out.println(s.maxProfit(prices));
    }
};

class Profit {
    int maxProfit, minPrice;
    Profit(int maxProfit, int minPrice) {
        this.maxProfit = maxProfit;
        this.minPrice = minPrice;
    }
}
```

Another Implementation with Dynamic Programming

```java
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }

        int[] left = new int[prices.length];
        int[] right = new int[prices.length];

        // DP from left to right;
        left[0] = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(prices[i], min);
            left[i] = Math.max(left[i - 1], prices[i] - min);
        }

        //DP from right to left;
        right[prices.length - 1] = 0;
        int max = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            max = Math.max(prices[i], max);
            right[i] = Math.max(right[i + 1], max - prices[i]);
        }

        int profit = 0;
        for (int i = 0; i < prices.length; i++){
            profit = Math.max(left[i] + right[i], profit);  
        }

        return profit;
    }
}
```

State Machine

```java
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        return maxProfit(prices, 2);
    }
    private int maxProfit(int[] array, int t) {
        int[] stock = new int[t * 2];
        Arrays.fill(stock, Integer.MIN_VALUE);
        stock[0] = -array[0];
        for(int i = 1; i < array.length; ++i) {
            stock[0] = Math.max(stock[0], -array[i]);
            for (int j = 1; j < 2 * t; j += 2) {
                stock[j] = Math.max(stock[j], stock[j - 1] + array[i]);
                if (j + 1 < 2 * t) {
                    stock[j + 1] = Math.max(stock[j + 1], stock[j] - array[i]);
                }
            }
        }
        return Math.max(0, stock[2 * t - 1]);
    }
}
```

## Reference

<http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html>\
<http://www.jiuzhang.com/solutions/best-time-to-buy-and-sell-stock-iii/>


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://aaronice.gitbook.io/lintcode/high_frequency/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.