Best Time to Buy and Sell Stock III

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

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

C++实现代码：

```#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
int maxProfit(vector<int> &prices) {
if(prices.empty())
return 0;
int n=prices.size();
int i;
int low=prices[0];
int left[n];
left[0]=0;
for(i=1;i<n;i++)
{
low=min(low,prices[i-1]);
left[i]=max(left[i-1],prices[i]-low);
}
int high=prices[n-1];
int right[n];
right[n-1]=0;
for(i=n-2;i>=0;i--)
{
high=max(high,prices[i+1]);
right[i]=max(right[i+1],high-prices[i]);
}
int maxSum=0;
for(i=0;i<n;i++)
{
maxSum=max(maxSum,left[i]+right[i]);
}
return maxSum;
}
};

int main()
{
Solution s;
vector<int> vec={1,4,6,8,3,5,9,3,6};
cout<<s.maxProfit(vec)<<endl;
}```

+ 关注