题目描述

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

题解一

使用暴力法的话，直接双重循环找出每一对利润的差值，比较大小即可。

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

题解二

第二种思路是扫描一遍价格数组，在扫描到数组的第i个数字时，保存之前i-1个数字中的最小值，这个最小值就是买入的最佳时间点，然后就可以算出卖出时的最大利润。

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