暴力法比较直接,贪心法比较美丽。

为啥可以用贪心呢?因为买必须在卖之前,因此每到一步都可以获取到这一步为止的最佳状态,不断这个最佳状态即可。

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