普通暴力解

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 upStack = new Stack();
    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 minWindow = new LinkedList();
    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;
}

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