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

 
设dpBack[i]为从第一天到第i天的最大的收益
设dpAfter[j]为从第j天到最后一天的最大收益
 
如何求最大收益可以考虑采用Best Time to Buy and Sell Stock I的方法
 
注意是最多买两次,也可以只买一次
 
 class Solution {
public:
int maxProfit(vector<int> &prices) { int n=prices.size();
if(n==)return ; vector<int> dpBack(n),dpAfter(n); int maxProfit=;
dpBack[]=;
int left=prices[]; for(int i=;i<n;i++)
{
if(prices[i]>left)
{
if(maxProfit<prices[i]-left) maxProfit=prices[i]-left;
}
else
{
left=prices[i];
} dpBack[i]=maxProfit;
} maxProfit=;
dpAfter[n-]=;
int right=prices[n-]; for(int j=n-;j>=;j--)
{
if(prices[j]<right)
{
if(maxProfit<right-prices[j]) maxProfit=right-prices[j];
}
else
{
right=prices[j];
} dpAfter[j]=maxProfit;
} int result=;
for(int i=;i<n-;i++)
{
if(dpBack[i]+dpAfter[i+]>result) result=dpBack[i]+dpAfter[i+]; if(result<dpBack[i+]) result=dpBack[i+];
} return result;
}
};
上一篇:【leetcode】123. Best Time to Buy and Sell Stock III


下一篇:java后端模拟表单提交