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).
1 两段分段思想
2 前往后，后往前都可以处理数列的思想
时间复杂度是O(n)，不掌握这种思想是很难做出来的。
class Solution {
public:
int maxProfit(vector<int> &prices)
{
vector<int> profit(prices.size()+1);
int buy = INT_MAX;
for (int i = 0; i < prices.size(); i++)
{
if (prices[i] < buy) buy = prices[i];
else profit[i+1] = max(profit[i], prices[i]-buy);
}
int sale = INT_MIN , max_profit = 0, res = 0;
for (int i = prices.size() - 1; i >= 0 ; i--)
{
if (prices[i] > sale) sale = prices[i];
else max_profit = max(max_profit, sale - prices[i]);
profit[i+1] = profit[i+1]+ max_profit;
res = max(profit[i+1], res);
}
return res;
}
};