Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

思路：可以看成是一个典型的DP问题，根据给出的股票每天的价格，算出当天与前一天之间的盈亏。然后求出此数组的最大子数组和

其实也可以在n^2的时间内解决问题，在某一天卖出，在以后的任何一天卖出，计算出最大的盈利。没有空间复杂度。

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

int BestTimeToSell(vector<int>& vec)
{
	vector<int> share(vec.size(),0);
	int i;
	for(i=1;i<vec.size();i++)
		share[i] = vec[i]-vec[i-1];
	
	int sum=share[0];
	int cur =share[0];
	for(i=1;i<share.size();i++)
	{
		if(cur < 0)
			cur = share[i];			
		else
			cur += share[i];
		if(cur > sum )
			sum = cur;
		
	}	
	return sum < 0? 0:sum;
}

int main()
{
	int array[]={12,8,10,6,15,18,10};
	vector<int> vec(array,array+sizeof(array)/sizeof(int));
	
	
	cout<<BestTimeToSell(vec);
	return 0;
}