**一. 題目描述** Say you have an array for which the i-th 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. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). **二. 題目分析** 和前兩道題相比，這道題限制了股票的交易次數，最多只能交易兩次。 可使用動態規劃來完成，首先是進行第一步掃描，先計算出序列`[0, …, i]`中的最大利潤`profit`，用一個數組`f1`保存下來，這一步時間復雜度為`O(n)`。 第二步是逆向掃描，計算子序列`[i, …, n - 1]`中的最大利潤`profit`，同樣用一個數組`f2`保存下來，這一步的時間復雜度也是`O(n)`。 最后一步，對于，對`f1 + f2`，找出最大值即可。 **三. 示例代碼** ~~~ #include <iostream> #include <vector> using namespace std; class Solution { public: int maxProfit(vector<int> &prices) { int size = prices.size(); if (size <= 1) return 0; vector<int> f1(size); vector<int> f2(size); int minV = prices[0]; for (int i = 1; i < size; ++i) { minV = std::min(minV, prices[i]); f1[i] = std::max(f1[i - 1], prices[i] - minV); } int maxV = prices[size - 1]; f2[size - 1] = 0; for (int i = size-2; i >= 0; --i) { maxV = std::max(maxV, prices[i]); f2[i] = std::max(f2[i + 1], maxV - prices[i]); } int sum = 0; for (int i = 0; i < size; ++i) sum = std::max(sum, f1[i] + f2[i]); return sum; } }; ~~~ **四. 小結** 相比前兩題，該題難度稍大，與該題相關的題目有好幾道。后續更新…