剑指Offer63.股票最大利润

原题链接

思路：本题有点贪心算法的感觉，由题意可以确定的是卖一定在买之后，也就是说我们只需要任选一天作为中介，在它当天或它之前买入，在它当天或它之后卖出，这就是题意了。那如何下手呢，要求的是最大利润，计算公式就是卖价减去买价，也就是说卖价越高越好，买价越低越好，但是我们不知道以哪一天做为那个中介，因此我们可以对于每一天，计算在这一天及之前买入股票的最低价，并计算在这天及之后卖出的最高价，然后将卖价与买价相减，就既可以保证卖在买之后，还能保证求出最优解。

参考代码如下

public static int min(int a, int b) {
        return a < b ? a : b;
    }

    public static int max(int a, int b) {
        return a > b ? a : b;
    }

    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[] left = new int[len];
        int[] right = new int[len];
        if(len > 0) {
            left[0] = prices[0];
            right[len - 1] = prices[len - 1];
        }
        for(int i = 1; i < len; i ++) {
            left[i] = min(left[i - 1], prices[i]);
            right[len - 1 - i] = max(right[len - i], prices[len - 1 - i]);
        }
        int ans = 0;
        for(int i = 0; i < len; i ++) {
            ans = max(ans, right[i] - left[i]);
        }
        return ans;
    }