Best_time_to_buy_and_sell_stock_I

/*
Best Time to Buy and Sell Stock 
Say you have an array for which the ith 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.
*/
class Solution {
public:
    int maxProfit(vector<int> &prices) {
    	if (prices.size()==0) return 0;
        int min=prices[0], GlobalMaxProfit=0;
	for (int i=0; i<prices.size(); ++i)
	{
	  if (prices[i]<min) min=prices[i];
	  int CurrentMaxProfit=prices[i]-min;
	  if (CurrentMaxProfit>GlobalMaxProfit) GlobalMaxProfit=CurrentMaxProfit;
	}
	return GlobalMaxProfit;
    }
};

1.REMARK: Hard one. First, I used the naive method at below which cost O(n^2) and time limit exceeded.

IDEA:Scan from left to the right.For each element,keep track of the minimum element to its left. Just O(1) for each element, since just a comparison.Then, for each element, only calculate the difference between current price and minimal price.If this diff large than the current max difference, replace it. 
2. Time complexity: O(n)
3. Below is the naive method, should be discarded.


class Solution {
public:
    int maxProfit(vector<int> &prices) {
      if (prices.size()==0) return 0;
      int profit=0;
      for (int i=0; i<prices.size()-1; ++i)
      {
        for (int j=i+1; j<prices.size();++j)
	{
	  int temp=prices[j]-prices[i];
	  if (temp>profit) profit=temp;
	}
      } 
      return profit; 
    }
};