121.Best Time to Buy and Sell Stock (E) 这题出奇地高频

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.

Solution1: DP O(n); O(1)

    /**
     * Solution1: DP O(n); O(1)
     * Max profit = max price - min price.
     * Use two variables to record min price and max profit.
     * Traverse the array. Min price is the larger one between itself and current price.
     * Max profit is the larger one between itself and current price – min price.
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int max = 0;
        int minPrice = prices[0];
        for (int curPrice : prices) {
            minPrice = Math.min(minPrice, curPrice);
            max = Math.max(max, curPrice - minPrice);
        }
        return max;
    }

Solution 2: Kadane's Algorithm O(n); O(1)

    /**
     * Kadane's Algorithm O(n);O(1)
     * The logic to solve this problem is same as "max subarray problem" using Kadane's Algorithm. Since no body has mentioned this so far,
     * I thought it's a good thing for everybody to know. All the straight forward solution should work,
     * but if the interviewer twists the question slightly by giving the difference array of prices, Ex: for {1, 7, 4, 11},
     * if he gives {0, 6, -3, 7}, you might end up being confused. Here, the logic is to calculate the difference
     * (maxCur += prices[i] - prices[i-1]) of the original array, and find a contiguous subarray giving maximum profit.
     * If the difference falls below 0, reset it to zero.
     */
    public int maxProfitB(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int maxCur = 0;
        int maxSoFar = 0;
        for (int i = 1; i < prices.length; i++) {
            maxCur = Math.max(0, maxCur + prices[i] - prices[i - 1]);
            maxSoFar = Math.max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }

Follow Up:

1.lc 妖二妖的反过来，就是最大的drop 就是比如 5 9 6 1，返回9-1=8，最大的drop

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

        int min = 0;
        int maxPrice = prices[0];
        for (int curPrice : prices) {
            maxPrice = Math.max(maxPrice, curPrice);
            min = Math.min(min, curPrice - maxPrice);
        }
        return Math.abs(min);
    }