学步园

一、     题目

同样是买卖股票，求出最大的利润，不过只能买和卖一次。

二、     分析

既然是只能买卖一次，则买入肯定要在卖出前边，所以我们可以遍历数组，每次保存下来当前最大利润和当前最小值，每经过一个值，则用当前值减去前面的最小值和最大利润比较取较大，同时当前值和最小值比较取较小，直到结束。

注意:在遍历前一定要检查下数组的元素个数！

其他不错的方法: http://blog.csdn.net/ithomer/article/details/7107968

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

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