> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/123.-best-time-to-buy-and-sell-stock-iii.md).

# 123. Best Time to Buy and Sell Stock III

## 1.問題 

* 你擁有一個代表每天股票價格的list, 最多有兩次交易, 計算出最高的獲利價格

![](/files/-L_gKUNs0uf3f5lyzO5s)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 確認題意: &#x20;
* function header, parameter
* test input
* 觀察
  \*
* 說明想法
  * 對某天來說的最大獲利是在該天賣掉, 當天再次買進
  * 區域最高獲利 (每天的最高獲利)
    * 第一次買剛好是第一次賣前的最低價格
    * 第二次賣正好是第一次賣後的最高價格
  * 找出區域最大獲利中的最大值
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        if (size < 2) {
            return 0;
        }
        
        //對某一天來說, 第一次交易 (該天價格 - 最小價格)
        vector<int> first(prices.size(), 0);
        int minV = prices[0];
        for (int i = 1; i < size; i++) {
            first[i] = max(first[i - 1], (prices[i] - minV));
            minV = min(minV, prices[i]);
        }
        
        //對某一天來說, 第二次交易 (最大價格 - 該天價格)
        int maxV = prices[size - 1];
        int res = 0;
        for (int i = size - 2; i >= 0; i--) {
            maxV = max(maxV, prices[i]);
            res = max(res, (maxV - prices[i] + first[i]));
        }
        
        return res;
    }
};
```