首页 > 代码库 > Leetcode:best_time_to_buy_and_sell_stock

Leetcode:best_time_to_buy_and_sell_stock

一、     题目

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

二、     分析

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

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

 

其他不错的方法: 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;
    }
};


Leetcode:best_time_to_buy_and_sell_stock