[数组]121. Best Time to Buy and Se

题目：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.

和122 Best Time to Buy and Sell Stock 差不多。区别在于只能买一次卖一次，所以要先找到最小值然后找到最大值。

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len == 0) return 0;
        int profit = 0;
        int min = prices[0];
        
        for(int i =1; i<len ;i++){
            if(prices[i]> min) {
                profit = Math.max(profit, prices[i] - min);
            }else{
                min = prices[i];
            }
        }
        return profit;
    }
}

参考优化版：

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1) return 0;
        int min = prices[0];
        int res = 0;
        for(int i = 1; i<prices.length; i++ ){
            if (prices[i] - min > res && prices[i] > min){
                res = prices[i] - min;
            }
            min = Math.min(prices[i],min);
            
        }
        return res;
    }
}