# [leetcode] Best Time to Buy and Sell Stock III

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

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

tag: dynamic programming

maxLeftProfit[i]表示从开始到第i天为止，完成一次交易的最大的利润的值；

maxRightProfit[i]表示从第i天到结束为止，完成一次交易的最大的利润的值。

maxLeftProfit[i] + maxRightProfit[i]就表示以第i天为分界线，之前和之后各完成一次交易的最大利润的和。

```class Solution {
public:
int maxProfit(vector<int> &prices) {
if(prices.empty()){
return 0;
}
size_t n = prices.size();
vector<int> maxLeftProfit = vector<int>(n, 0);// 在第i天时，左侧交易可达成的最大利润
vector<int> maxRightProfit = vector<int>(n, 0);// 在第i天时，右侧交易可达成的最大利润
int minV = prices[0];
int maxV = prices[n - 1];
for(int i = 1; i < n; i++){//构建两个数组，maxLeftProfit, maxRightProfit
maxLeftProfit[i] = max(maxLeftProfit[i - 1], prices[i] - minV);//这实际是sell stock I的代码，完成一次交易可达成的最大利润
minV = prices[i] < minV? prices[i]: minV;

maxRightProfit[n - i] = max(maxRightProfit[n - i - 1], maxV - prices[n - i]);
maxV = prices[n - i] > maxV? prices[n - i]: maxV;
}
int sum = 0;
for(int i = 0; i < n; i++){
int thisSum = maxLeftProfit[i] + maxRightProfit[i];
sum = thisSum > sum? thisSum:sum;
}
return sum;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.