Best Time to Buy and Sell Stock III
最后更新于：2022-04-01 22:57:20
**一. 题目描述**
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
#include
using namespace std;
class Solution {
public:
int maxProfit(vector &prices)
{
int size = prices.size();
if (size <= 1) return 0;
vector f1(size);
vector 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;
}
};
~~~
**四. 小结**
相比前两题，该题难度稍大，与该题相关的题目有好几道。后续更新…
';