/****************************
   Name:  Best time to sell stock III 
   Date: 01/30/2016
   Author: Hualin Li
   Description: This is the Best time to sell stock III in the C++. 还是DP大法
   做题感想：该题目初看时比I,II还吓人，笔者想了两天才想通这个网上流行的算法答案。
   原则上只要扫一遍vector就可以了，但是分两步进行，第一步顺序扫描，完全是I的做法。
   难理解的是第二步，逆序扫描。这步的作用是找出另一半里面的可能最大值。
   
   值得注意的是，里面很巧妙的运用了一个叫profit的vector来储存sum和sum2，大家只要记住
   一点，顺序扫描后，顺序的最大profit放在了profit（i）中，逆序扫描只是叠加上去而已。
   实在不明白的，搞一个数组来画画就懂了。自己也是在曼哈顿M9摇摇晃晃的公车上才想通的。
   
*****************************/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
		int length=prices.size();
		if(length<=1)
			return 0;
		
		int minP=prices[0];
		int sum=INT_MIN;
		vector <int> profit;
		profit.resize(length);
		
		for(int i=1;i<length;i++)
		{
			minP=min(minP,prices[i-1]);
			sum=max(sum,prices[i]-minP);
			//Remember for ith, profit[i] will be the same
			profit[i]=sum;
		}
		//The reverse scan
		int maxP=prices[length-1];
		int sum2=INT_MIN;
		for(int j=length-2;j>=0;j--)
		{
			maxP=max(maxP,prices[j+1]);
			sum2=max(sum2,maxP-prices[j]);
			//To add two sum
			if(sum2>0)
			{
				profit[j]=profit[j]+sum2;
				sum=max(profit[j],sum);
			}
		}
		
		if(sum>0)
		return sum;
	    else
		return 0;
		
    }
};