121. Best Time to Buy and Sell Stock

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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 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
Explanation: In this case, no transaction is done, i.e. max profit = 0.

My Solutions:

储存一个最小数并随时更新，用dp【】储存每一步减最小数获得的最大利润

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

优化：观察上面的dp，发现只需要一个min和dp【i-1】，因此，可以优化到用maxprofit 代替dp【i-1】储存最大利润

class Solution {
    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;
        
    }
}

上面的if-else block也可以换个写法

if (prices[i] > minprice) { // 发现当前值比最小值大，更新最大利润
    maxprofit = Math.max(maxprofit, p[i] - minprice);
} else { // 发现当前值比最小值小，更新最小值
    minprice = p[i];
}