算法：买卖股票的最佳时机

题目

给定一个数组prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。

你只能选择某一买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。

实现

方法一

1. 记录【今天之前买入的最小值】
2. 计算【今天之前最小值买入，今天卖出的获利】，也即【今天卖出的最大获利】
3. 比较【每天的最大获利】，取最大值即可

public static int maxProfit(int[] prices) {
    int min = prices[0];
    int maxProfit = 0;

    for (int i = 1; i < prices.length; i++) {
        int profit = prices[i] - min;
        maxProfit = Math.max(profit, maxProfit);
        min = Math.min(min, prices[i]);
    }
    return maxProfit;
}

方法二

暴力比较

public static int maxProfit(int[] prices) {
    int maxProfit = 0;
    for (int i = 0; i < prices.length - 1; i++) {
        for (int j = i + 1; j < prices.length; j++) {
            if (prices[j] > prices[i]) {
                maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
            }
        }
    }
    return maxProfit;
}

超出时间限制。- -!

LeetCode 原题地址

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/comments