学步园

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

现在条件变成了最多两次，一个直接的思路是枚举切分点，然后分别计算前后只能买一次的最大值，相加；当然也可能整个只买一次。

直观看复杂度是o(n2)的，试了下大数据果然是过不了~

其实遇到这种最多两次的题，要敏感，最多两次跟最多K次还不一样，最多两次的题通常都可以转化为一次的情况，即前向扫描一遍，保留profit[i],再后向扫描一遍，扫描到i的时候，就是这次扫描的最大值加前向扫描的那个profit[i]之和。

代码：

class Solution {
public:
    int maxProfit(vector<int>& price)
	{
		int n=price.size();
		if (n<=1)
			return 0;
		vector<int> profit(n,0);
		int low=price[0],i;
		for(i=1;i<n;i++)
		{
			if (price[i]>low)
			{
				profit[i]=max(profit[i-1],price[i]-low);
			}
			else
			{
				profit[i]=profit[i-1];
				low=price[i];
			}
		}
		int high=price[n-1];
		int ans=0;
		for(i=n-1;i>=0;i--)
		{
			if (high>price[i])
			{
				ans=max(ans,profit[i]+high-price[i]);
			}
			else
				high=price[i];
		}
		return ans;
	}
};

人家一样的思路为什么16ms过大合集，我的要60ms啊！！！！！ 

是因为使用了max函数吗？ 哪位同学知道