/****************************
   Name:  Best time to sell stock I 
   Date: 01/30/2016
   Author: Hualin Li
   Description: This is the Best time to sell stock I in the C++. 还是DP大法
   做题感想：该题目初看时比较吓人，仔细一想只要扫一遍vector就可以了。只要动态的记录最小值，
   并且同时计算最大利润即可。
   
*****************************/
class Solution {
public:
    int maxProfit(vector <int>& prices) {
    //This line is very important, without it leetcode run time error
    if(prices.size() <= 1) {
            return 0;
        }


      int minP=prices[0];
      int mProfit=prices[1]-prices[0];
        //Remember the index
      for(int i=2;i<prices.size();i++)
      {
          minP=min(minP,prices[i-1]);
          mProfit=max(mProfit,prices[i]-minP);

      }
        
        if(mProfit<0)
        return 0;

        return mProfit;
    }
};