买卖股票的最好时机

题目链接

Solution

因为只有一次买入卖出的机会，所以可以枚举在哪天卖出。
对于卖出的那一天，买入的那一天一定在这一天之前，并且是价格最低的。
所以从前往后扫，记录并更新最小值即可。

Code

class Solution {
public:

    int maxProfit(vector<int>& prices) {
        // write code here?
        int ans = 0, mn = prices[0];
        for (int i = 1; i < (int)prices.size(); ++i) {
            ans = max(ans, prices[i] - mn);
            mn = min(mn, prices[i]);
        }
        return ans;
    }
};