算法

(贪心) $O(n)$

• 从左到右遍历每天的价格
• 如果以当天之前的最低价买入，以当天价格卖出，那么就得到了当天卖出的最大利润
• 在每一天卖出的最大利润中找到最大值

Java 代码

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;

        // 为什么用Integer.MAX_VALUE?
        // 因为需要一个极大值保证第一个交易日不产生maxProfit
        int previousMinPrice = Integer.MAX_VALUE;
        // 为什么不用Integer.MIN_VALUE?
        // 因为可以不交易，不交易的profit是0，所以最小值是0
        // 如果必须交易，那么这个初始值应该是Integer.MIN_VALUE
        int maxProfit = 0;

        for (int currPrice : prices) {
            // 更新maxProfit
            maxProfit = (currPrice - previousMinPrice) > maxProfit ?
            currPrice - previousMinPrice : maxProfit;
            // 更新当前为止的最小price
            previousMinPrice = currPrice < previousMinPrice ?
            currPrice : previousMinPrice;
        }

        return maxProfit;
    }
}