题解 | #买卖股票的最好时机(一)#

刚开始考虑这题：从左到右遍历，考虑每次新进的一个元素：

1. 如果i < min 或 i > max, 修改min 或 max；
2. 再考虑当前值与最小值的差是否大于利润
3. 最后考虑max<min的情况

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        if(prices.size() < 2)
            return 0;
        int pro = 0, max = 0, min = 0;
        for(int i = 1; i < prices.size(); i ++){
            if(prices[i] < prices[min])
                min = i;
            else if(prices[i] > prices[max])
                max = i;
            if(prices[i] - prices[min] > pro)
                pro = prices[i] - prices[min];
        }
        if(max > min)
            pro = pro > (prices[max] - prices[min]) ? pro : (prices[max] - prices[min]);
        return pro;
    }
};

改进：

只需要更新最小值，并计算当前值与最小值的差来维护最大利润

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        if(prices.size() < 2)
            return 0;
        int pro = 0, min = 0;
        for(int i = 1; i < prices.size(); i ++){
            if(prices[i] < prices[min])
                min = i;
            if(pro < prices[i] - prices[min])
                pro = prices[i] - prices[min];
        }
        return pro;
    }
};