买卖股票的最佳时机（多解法）

　　普通暴力解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; }
　　以上花式炫技，你学废了吗？