[LeetCode]--121. Best Time to Buy and Sell Stock

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.

思路首先：动态规划
遍历数组时记录当前价格以前的最小价格curMin，记录昨天能够获得的最大利润maxProfit。对于今天，为了能获得此刻的最大利润，显然只能卖，或者不做任何操作。如果不做任何操作，显然还是昨天maxProfit。如果卖掉今天天的股票，显然prices[i]-curMin。

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