Say you have an array for which the ith
element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
Input: [7, 1, 5, 3, 6, 4]Output: 5max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]Output: 0In this case, no transaction is done, i.e. max profit = 0.
Subscribe to see which companies asked this question.

題目

假設(shè)有一個(gè)數(shù)組，它的第i個(gè)元素是一支給定的股票在第i天的價(jià)格。如果你最多只允許完成一次交易(例如,一次買(mǎi)賣股票),設(shè)計(jì)一個(gè)算法來(lái)找出最大利潤(rùn)。
樣例
給出一個(gè)數(shù)組樣例 [3,2,3,1,2], 返回 1

Solution

Approach #1 (Brute Force) 暴力搜索

思路很簡(jiǎn)單，我們就要找出數(shù)組中，差值最大的兩個(gè)數(shù)，要求是前一個(gè)數(shù)小，后一個(gè)數(shù)大，那么遍歷兩邊即可，找出所有這樣的差值，找出其中最大的一個(gè)

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 貪婪法

通過(guò)一遍遍歷，找出到此為止之前最小的min,并與當(dāng)前的值求差，保存最大的差值，遍歷完，最后的差值即是最大差值。

Paste_Image.png

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;
    }