题解 | #牛群售价预测#

知识点

贪心

思路

由题意可知，为了得到最大利润，需要从左往右遍历，维护最小price[i]与其右侧的最大price[i+?]。

所以我们只需要使用minn来维护最小的price[i]作为购入价。

在向右遍历的过程中：

遇到price[i]-minn的情况就更新ans=max(ans,price[i]-minn)

遇到price[i]<minn的情况就更新minn,一次遍历即可得到最大ans。

返回时若ans>0则返回ans，否则返回0。

代码c++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int max_profit(vector<int>& prices) {
        // write code here
        int ans=0;
        int n=prices.size();
        int minn=prices[0];
        for(int i=0;i<prices.size();i++)
        {            
                minn=min(minn,prices[i]);
                if(prices[i]>minn)
                {
                    ans=max(ans,prices[i]-minn);
                }

        }
        return ans>0?ans:0;
    }
};