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: 5
max. 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: 0
In this case, no transaction is done, i.e. max profit = 0.

題意：用一個(gè)數(shù)組表示股票每天的波動(dòng)價(jià)格，如果你只有一次買(mǎi)賣(mài)的機(jī)會(huì)，那么你能賺到的最大利潤(rùn)是多少。

思路：
第一種思路，是以每個(gè)價(jià)格作為買(mǎi)入價(jià)格，然后再它后面找最高的賣(mài)出價(jià)格，通過(guò)兩次循環(huán)可以算出，時(shí)間復(fù)雜度是n方。

第二種思路，實(shí)際上每個(gè)價(jià)格都作為買(mǎi)入價(jià)格是不必要的，比如[2，3，9，20]，3和9都比2大，所以以3和9作為買(mǎi)入價(jià)格，肯定沒(méi)有以2獲取的利潤(rùn)多。由此想到只需要知道當(dāng)前最低的買(mǎi)入價(jià)格，如果當(dāng)前價(jià)格比最低價(jià)格還低，那么更新最低價(jià)格；如果比最低價(jià)格高，那么算一下以當(dāng)前價(jià)格作為賣(mài)出價(jià)格的利潤(rùn)，再與最大利潤(rùn)值比較。

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }

    int curMin = prices[0];
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > curMin) {
            profit = Math.max(profit, prices[i] - curMin);
        } else {
            curMin = prices[i];
        }
    }

    return profit;
}