普通暴力解

public int maxProfit(int[] prices) {    if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) {        return 0;    }    int ans = 0;    for (int i = 0; i < prices.length - 1; i++) {        for (int j = i + 1; j < prices.length; j++) {            if (prices[j] > prices[i]) {                ans = Math.max(ans, prices[j] - prices[i]);            }        }    }    return ans;}

暴力递归解

public int maxProfit(int[] prices) {    if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) {        return 0;    }    return process(prices, 0, -1, -1);}public int process(int[] prices, int i, int buyDay, int sellDay) {    if (prices.length == i) {        if (buyDay > -1 && buyDay < sellDay && prices[buyDay] < prices[sellDay]) {            return prices[sellDay] - prices[buyDay];        }        return 0;    }    // 在第i天不操作    int p0 = process(prices, i + 1, buyDay, sellDay);    // 在第i天买入    int p1 = 0;    if (buyDay == -1 && sellDay == -1) {        p1 = process(prices, i + 1, i, sellDay);    }    // 在第i天卖出    int p2 = 0;    if (buyDay > -1 && sellDay == -1) {        p2 = prices[i] > prices[buyDay] ? prices[i] - prices[buyDay] : 0;    }    return Math.max(p0, Math.max(p1, p2));}

另一种暴力递归可推导出动态规划：

public int maxProfit(int[] prices) {    if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) {        return 0;    }    return process(prices, 0, 0);}public int process(int[] prices, int i, int flag) {    // base case    if (i == 0) {        if (flag == 0) {            return 0;        }        return -prices[0];    }    if (flag == 0) { // 第i天不持有股票        return Math.max(process(prices, i - 1, 1) + prices[i], process(prices, i - 1, 0));    } else {        return Math.max(process(prices, i - 1, 1), -prices[i]);    }}

动态规划解

public int maxProfit(int[] prices) {    if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) {        return 0;    }    int len = prices.length;    // dp[i][0] 下标为 i 这天结束的时候，不持股，手上拥有的现金数    // dp[i][1] 下标为 i 这天结束的时候，持股，手上拥有的现金数    int[][] dp = new int[len][2];    // 初始化：不持股显然为 0，持股就需要减去第 1 天（下标为 0）的股价    dp[0][0] = 0;    dp[0][1] = -prices[0];    // 从第 2 天开始遍历    for (int i = 1; i < len; i++) {        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);        dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);    }    return dp[len - 1][0];}

在暴力递归的基础上加缓存，转变成记忆化搜索：

最终版的动态规划是怎么写出来的呢？请看下图：

单调栈解

public int maxProfit(int[] prices) {    if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) {        return 0;    }    int ans = 0;    //int min = 0;    //Stack<Integer> upStack = new Stack<Integer>();    int topIndex = -1; // 记录栈顶下标    int[] upStack = new int[prices.length];        for (int i = 0; i < prices.length; i++) {        // 由小到大的单调栈        //while (!upStack.empty() && upStack.peek() > prices[i]) {        while (topIndex > -1 && upStack[topIndex] > prices[i]) {            //int p = upStack.pop();            int p = upStack[topIndex--];            int min = upStack[0];            if (p > min) {                ans = Math.max(ans, p - min);            }        }        /*if (upStack.empty()) {            min = prices[i];        }*/        //upStack.push(prices[i]);        upStack[++topIndex] = prices[i];    }    // 栈顶元素未被处理    //if (upStack.size() > 1) {    if (topIndex > 0) {        //int p = upStack.pop();        int p = upStack[topIndex--];        int min = upStack[0];                if (p > min) {            ans = Math.max(ans, p - min);        }    }    return ans;}

直接使用 java.util.Stack 会对性能会造成影响，因此这里利用数组来优化。

滑动窗口解

public int maxProfit(int[] prices) {    if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) {        return 0;    }    // minWindow 由小到大    LinkedList<Integer> minWindow = new LinkedList<Integer>();    for (int R = 0; R < prices.length; R++) {        while (!minWindow.isEmpty() && prices[minWindow.peekLast()] >= prices[R]) {            minWindow.pollLast();        }        minWindow.addLast(R);        int buyPrice = prices[minWindow.peekFirst()];        int sellPrice = prices[R];        if (sellPrice > buyPrice) {            ans = Math.max(ans, sellPrice - buyPrice);        }    }    return ans;}

线段树解

public int maxProfit(int... prices) {    if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0] >= prices[1])) {        return 0;    }    int ans = 0;    SegmentTree segmentTree = new SegmentTree(prices);    for (int i = 0; i < prices.length; ++i) {        int buyPrice = prices[i];        int sellPrice = segmentTree.query(i + 1, prices.length, 1, prices.length, 1);        ans = Math.max(ans, sellPrice - buyPrice);    }    return ans;}public class SegmentTree {    private int[] data;    private int[] max;    public SegmentTree(int[] src) {        int N = src.length + 1;        data = src;        max = new int[N << 2];        build(1, N - 1, 1);    }    private void pushUp(int i) {        max[i] = Math.max(max[i << 1], max[i << 1 | 1]);    }    private void pushDown(int i) {    }    private void build(int l, int r, int i) {        if (l == r) {            max[i] = data[l - 1];            return;        }        int mid = (l + r) >> 1;        build(l, mid, i << 1);        build(mid + 1, r, i << 1 | 1);        pushUp(i);    }    public int query(int L, int R, int l, int r, int i) {        if (L <= l && r <= R) {            return max[i];        }        int mid = (l + r) >> 1;        pushDown(i);        int left = 0;        int right = 0;        if (L <= mid) {            left = query(L, R, l, mid, i << 1);        }        if (R > mid) {            right = query(L, R, mid + 1, r, i << 1 | 1);        }        return Math.max(left, right);    }}

树状数组解

public int maxProfit(int[] prices) {    if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) {        return 0;    }    int ans = 0;    IndexTree indexTree = new IndexTree(prices.length);    for (int i = 0; i < prices.length; i++) {        indexTree.set(i + 1, prices[i]);    }    for (int i = 1; i < prices.length; i++) {        int min = indexTree.min(i + 1);        if (prices[i] > min) {            ans = Math.max(ans, prices[i] - min);        }    }    return ans;}public static class IndexTree {    private int[] tree;    private int N;    // 0位置弃而不用    public IndexTree(int size) {        N = size;        tree = new int[N + 1];        for (int i = 1; i <= N; i++) {            tree[i] = Integer.MAX_VALUE;        }    }    // 返回 [1, index] 范围最小值    public int min(int index) {        int ret = Integer.MAX_VALUE;        while (index > 0) {            ret = Math.min(tree[index], ret);            index -= index & -index;        }        return ret;    }    // index & -index : 提取出index最右侧的1出来    // 假设 index 为   : 0011001000    // index & -index : 0000001000    public void set(int index, int v) {        while (index <= N) {            tree[index] = Math.min(tree[index], v);            index += index & -index;        }    }}

最优解

public int maxProfit(int[] prices) {    if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) {        return 0;    }    int ans = 0;    int minPre = prices[0];    for (int i = 1; i < prices.length; i++) {        if (prices[i] > minPre) {            ans = Math.max(ans, prices[i] - minPre);        } else {            minPre = prices[i];        }    }    return ans;}

以上花式炫技，你学废了吗？