题目

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

Solution

Approach #1 (Brute Force) 暴力搜索

思路很简单，我们就要找出数组中，差值最大的两个数，要求是前一个数小，后一个数大，那么遍历两边即可，找出所有这样的差值，找出其中最大的一个

public 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++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit)
                    maxprofit = profit;
            }
        }
        return maxprofit;
    }

Approach #2 (One Pass) Greedy 贪婪法

通过一遍遍历，找出到此为止之前最小的min,并与当前的值求差，保存最大的差值，遍历完，最后的差值即是最大差值。

public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice)
                minprice = prices[i];
            else if (prices[i] - minprice > maxprofit)
                maxprofit = prices[i] - minprice;
        }
        return maxprofit;
    }