！！！题解 | 买卖股票的最好时机(一) 贪心思路 妙 学之

#include <algorithm>
#include <climits>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        //暴力法 超时
        //这题关键是用贪心法融合进动态规划。
        /*
        由于买在卖前面，所以对每个元素来说 如果在这个元素卖出 买入的时机应该是这个元素前的最低点。
        可以用一个变量记录这个最低点。那么所有在这个最低点后面的元素都可以在这一点买入。
        同时 这个最低点是及时更新的 由于数组从左到右 卖出也在买入后面，所以【i】-最低点一定是这个元素卖出得到的最大收益。
        而因为不需要存储信息 所以只需要一个变量记录最大收益就行了
        */
        int size=prices.size();
        if (size<2) {
            return 0;
        }
        //int low=0;//不应该初始化为0，应该是price【0】
        int low=prices[0];
        //如果不能获取到任何利润，请返回0
        int res=0;
        for(int i=1;i<size;i++){
            int profit=prices[i]-low;
            res=max(res, profit);
            if(prices[i]<low)low=prices[i];
        }
        return res;
    }
};