买卖股票的最佳时机

题目描述

假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

思路

贪心。每访问一个数组的元素，都判断其是否为卖点，如果不是，判断其是否为买点，都不是，继续向后访问。

• 用buy和sell表示买卖点下标，res表示利润，初始都为0
• 从num[1]开始遍历数组元素
  • 如果出现卖点（当前值-买点值 大于 res），更新res，更新sell
  • 如果出现买点（当前值 < 买点），更新buy
• 遍历完数组，res即为最大利润
  这样做，利用贪心的思想，buy始终是当前最好的买点下标，sell始终是当前最好的卖点下标，res始终是当前最大的利润

代码

public int maxProfit(int[] prices) {
        int buy = 0;
        int sell = 0;
        int res = 0;
        for(int i = 1; i < prices.length; i++) {
            // 能卖吗
            if((prices[i] - prices[buy]) > res) {
                sell = i;
                res = prices[i] - prices[buy];
                continue;
            }
            // 能买吗
            if(prices[i] < prices[buy]) {
                buy = i;
                continue;
            }
        }
        return res;
    }

考察点

• 贪心