（算法）买卖股票的最佳时机————＜贪心算法＞

1. 题⽬链接：121.买卖股票的最佳时机

2. 题⽬描述：

3. 解法（贪⼼）：

贪⼼策略：

由于只能交易⼀次，所以对于某⼀个位置i ，要想获得最⼤利润，仅需知道前⾯所有元素的最⼩ 值。然后在最⼩值的位置「买⼊」股票，在当前位置「卖出」股票即可。

C++算法代码： 

class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        //返回值，第i位前的最小值
        int ret=0,min_num=prices[0];
        for(int i=1;i<prices.size();i++)
        {
            //更新最大差值
            if(prices[i]>min_num)
            {
                ret=max(ret,prices[i]-min_num);
            }
            //更新第i位前的最小值
            min_num=min(min_num,prices[i]);
        }
        return ret;
    }
};

Java算法代码：

class Solution
{
	public int maxProfit(int[] prices)
	{
		int ret = 0; // 记录最终结果 
		for (int i = 0, prevMin = Integer.MAX_VALUE; i < prices.length; i++)
		{
			ret = Math.max(ret, prices[i] - prevMin); // 先更新结果 
			prevMin = Math.min(prevMin, prices[i]); // 再更新最⼩值 
		}
		return ret;
	}
}