程序员算法实现买卖股票的最佳时机系列问题

　　LeetCode 121. 买卖股票的最佳时机#
　　主要思路：因为只有一股可以交易，所以我们可以枚举必须以i位置作为卖出时机的情况下，得到的最大收益是多少。如果我们得到每个i位置的最大收益，那么最大收益必是所有位置的最大收益的最大值。
　　使用两个变量：
　　min变量：表示遍历到的位置之前的最小值是什么。
　　max变量：表示当前收集到必须以i位置卖出的最大收益是多少。
　　遍历数组一遍，在遍历到i位置的时候，min和max的更新逻辑如下：min = Math.min(arr[i], min); // 每次遍历到的arr[i]和全局min进行比较，看能否刷新min的值 max = Math.max(arr[i] - min, max); // arr[i] - min 表示必须以i位置卖出时候的最大收益是什么，和全局的max值pk的最大值赋予max
　　遍历完数组，返回max的值就是最终答案。完整代码见：public class LeetCode_0121_BestTimeToBuyAndSellStock {     public int maxProfit(int[] arr) {         int max = 0;         int min = arr[0];         for (int i = 1; i < arr.length; i++) {             min = Math.min(arr[i], min);             max = Math.max(arr[i] - min, max);         }         return max;     } } LeetCode 122. 买卖股票的最佳时机 II#
　　主要思路：由于可以进行任意次的交易，但是任何时候最多只能持有一股股票，所以我们可以把股票曲线的所有上升段都抓取到，累加收益就是最大收益。遍历数组，遍历到的位置减去前一个位置的值，如果是正数，就收集，如果是负数，就把本次收益置为0（就等于没有做这次交易），这样遍历一遍数组，就不会错过所有的收益。
　　设置一个变量max，初始为0，用于收集最大收益值，来到i位置，max更新逻辑如下：max += Math.max((prices[i] - prices[i - 1]), 0);
　　完整代码如下：public int maxProfit(int[] prices) {    int max = 0;    for (int i = 1; i < prices.length; i++) {         // 把所有上坡都给抓到         max += Math.max((prices[i] - prices[i - 1]), 0);    }    return max; }
　　由本题可以简单得出一个结论：如果数组元素个数为N，则最多执行N/2次交易就可以抓取所有的上升段的值（极端情况下，当前时刻买，下一个时刻卖，保持这样的交易一直到最后，执行的交易次数就是N/2）。LeetCode 188. 买卖股票的最佳时机 IV#
　　主要思路：如果k的值大于等于数组长度的二分之一，就等于有无限次交易，在这样的情况下，可以直接用问题二的解法来做。如果k的值小于数组长度的二分之一，就需要单独考虑了。
　　在第2种情况下，我们定义int[][] dp = new int[N][k+1]
　　其中dp[i][j]表示[0...i]范围内交易j次获得的最大收益是多少。如果可以把dp这个二维表填好，那么返回dp[N-1][k]的值就是题目要的答案。
　　dp这个二维矩阵中，
　　第一行的值表示数组[0..0]范围内，交易若干次的最大收益，显然，都是0。
　　第一列的值表示数组[0...i]范围内，交易0次获得的最大收益，显然，也都是0。
　　针对任何一个普遍位置dp[i][j]的值，
　　我们可以枚举i位置是否参与交易，如果i位置不参与交易，那么dp[i][j] = dp[i-1][j]，如果i位置参与交易，那么i位置一定是最后一次的卖出时机。
　　那最后一次买入的时机，可以是如下情况：
　　最后一次买入的时机在i位置，那么dp[i][j] = dp[i][j-1] - arr[i] + arr[i]
　　最后一次买入的时机在i-1位置，那么dp[i][j] = dp[i-1][j-1] - arr[i-1] + arr[i]
　　最后一次买入的时机在i-2位置，那么dp[i][j] = dp[i-2][j-1] - arr[i-2] + arr[i]
　　...
　　最后一次买入的时机在0位置，那么dp[i][j] = dp[0][j-1] - arr[0] + arr[i]// i位置不参与交易，则dp[i][j]至少是dp[i-1][j] dp[i][j] = dp[i - 1][j]; for (int m = 0; m <= i; m++) {     // 枚举每次买入的时机     dp[i][j] = Math.max(dp[m][j - 1] - arr[m] + arr[i] , dp[i][j]); }
　　完整代码如下：public class LeetCode_0188_BestTimeToBuyAndSellStockIV {     public static int maxProfit(int k, int[] arr) {         if (arr == null || arr.length < 2) {             return 0;         }         int N = arr.length;         if (k >= N >> 1) {             return infinityMax(arr);         }         int[][] dp = new int[N][k + 1];         for (int i = 1; i < N; i++) {             for (int j = 1; j <= k; j++) {                 // i位置不参与交易，则dp[i][j]至少是dp[i-1][j]                 dp[i][j] = dp[i - 1][j];                 for (int m = 0; m <= i; m++) {                     // 枚举每次买入的时机                     dp[i][j] = Math.max(dp[m][j - 1] - arr[m] + arr[i], dp[i][j]);                 }             }         }         return dp[N - 1][k];     }       public static int infinityMax(int[] arr) {         int ans = 0;         for (int i = 1; i < arr.length; i++) {             ans += Math.max(arr[i] - arr[i - 1], 0);         }         return ans;     } }
　　上述代码中包含一个枚举行为dp[i][j] = dp[i - 1][j] + arr[i] - arr[i]; for (int m = 0; m <= i; m++) {    // 枚举每次买入的时机    dp[i][j] = Math.max(dp[m][j - 1] - arr[m] + arr[i], dp[i][j]); }
　　增加了时间复杂度，我们可以优化这个枚举。
　　我们可以举一个具体的例子来说明如何优化，
　　比如，
　　当我们求dp[5][3]这个值，我们可以枚举5位置是否参与交易，假设5位置不参与交易，那么dp[5][3] = dp[4][3]，假设5位置参与交易，那么5位置一定是最后一次的卖出时机。那最后一次买入的时机，可以是如下情况：
　　最后一次买入的时机在5位置，那么dp[5][3] = dp[5][2] - arr[5] + arr[5]
　　最后一次买入的时机在4位置，那么dp[5][3] = dp[4][2] - arr[4] + arr[5]
　　最后一次买入的时机在3位置，那么dp[5][3] = dp[3][2] - arr[3] + arr[5]
　　最后一次买入的时机在2位置，那么dp[5][3] = dp[2][2] - arr[2] + arr[5]
　　最后一次买入的时机在1位置，那么dp[5][3] = dp[1][2] - arr[1] + arr[5]
　　最后一次买入的时机在0位置，那么dp[5][3] = dp[0][2] - arr[0] + arr[5]
　　我们求dp[4][3]这个值，我们可以枚举4位置是否参与交易，假设4位置不参与交易，那么dp[4][3] = dp[3][3]，假设4位置参与交易，那么4位置一定是最后一次的卖出时机。那最后一次买入的时机，可以是如下情况：
　　最后一次买入的时机在4位置，那么dp[4][3] = dp[4][2] - arr[4] + arr[4]
　　最后一次买入的时机在3位置，那么dp[4][3] = dp[3][2] - arr[3] + arr[4]
　　最后一次买入的时机在2位置，那么dp[4][3] = dp[2][2] - arr[2] + arr[4]
　　最后一次买入的时机在1位置，那么dp[4][3] = dp[1][2] - arr[1] + arr[4]
　　最后一次买入的时机在0位置，那么dp[4][3] = dp[0][2] - arr[0] + arr[4]
　　比较dp[5][3]和dp[4][3]的依赖关系，可以得到如下结论：
　　假设在求dp[4][3]的过程中，以下递推式的最大值我们可以得到
　　dp[4][2] - arr[4]
　　dp[3][2] - arr[3]
　　dp[2][2] - arr[2]
　　dp[1][2] - arr[1]
　　dp[0][2] - arr[0]
　　我们把以上式子的最大值定义为best，那么
　　dp[5][3] = Math.max(dp[4][3],Math.max(dp[5][2] - arr[5] + arr[5], best + arr[5]))
　　所以dp[5][3]可以由dp[4][3]加速得到，
　　同理，
　　dp[4][3]可以通过dp[3][3]加速得到，
　　dp[3][3]可以通过dp[2][3]加速得到，
　　dp[2][3]可以通过dp[1][3]加速得到，
　　dp[1][3]可以很简单得出，dp[1][3]有如下几种可能性:
　　可能性1，1位置完全不参与，则int p1 = dp[0][3]
　　可能性2，1位置作为最后一次的卖出时机，买入时机是1位置int p2 = dp[1][2] + arr[1] - arr[1]
　　可能性3，1位置作为最后一次的卖出时机，买入时机是0位置int p3 = dp[0][2] + arr[1] - arr[0]
　　此时，best的值为int best = Math.max(p2 - arr[1], p3 - arr[1])
　　然后通过dp[1][3]加速dp[2][3]，通过dp[2][3]加速dp[3][3]......，所以二维dp的填写方式是按列填，
　　先填dp[1][0]，dp[1][2]一直到dp[1][k]，填好第一列；
　　然后填dp[2][0],dp[2][1]一直到dp[2][k]，填好第二列；
　　...
　　依次填好每一列，直到填完第N-1列。
　　枚举行为被优化，优化枚举后的完整代码如下：public class LeetCode_0188_BestTimeToBuyAndSellStockIV {      public static int maxProfit(int k, int[] arr) {         if (arr == null || arr.length < 2) {             return 0;         }         int N = arr.length;         if (k >= N >> 1) {             return infinityMax(arr);         }         int[][] dp = new int[N][k + 1];         for (int j = 1; j <= k; j++) {             int p1 = dp[0][j];             int best = Math.max(dp[1][j - 1] - arr[1], dp[0][j - 1] - arr[0]);             dp[1][j] = Math.max(p1, best + arr[1]);             for (int i = 2; i < N; i++) {                 p1 = dp[i - 1][j];                 best = Math.max(dp[i][j - 1] - arr[i], best);                 dp[i][j] = Math.max(p1, best + arr[i]);             }         }         return dp[N - 1][k];     }      public static int infinityMax(int[] arr) {         int ans = 0;         for (int i = 1; i < arr.length; i++) {             ans += Math.max(arr[i] - arr[i - 1], 0);         }         return ans;     } } LeetCode 123. 买卖股票的最佳时机 III#
　　主要思路：上一个问题中，令k=2就是本题的答案。LeetCode 309. 最佳买卖股票时机含冷冻期#
　　主要思路：因为有了冷冻期，所以每个位置的状态有如下三种：冷冻期持有股票不持有股票，不在冷冻期
　　定义三个数组，分别表示i位置这三种情况下的最大值是多少// 处于冷冻期 int[] cooldown = new int[N]; // 持有股票 int[] withStock = new int[N]; // 不持有股票，也不处于冷冻期 int[] noStock = new int[N];
　　显然有如下结论：// 0位置需要处于冷冻期，说明0位置买了又卖掉，收益是0 cooldown[0] = 0;  // 0位置需要持有股票，只有可能在0位置买了一股，这个时候收益为0-arr[0] withStock[0] = -arr[0]; // 0位置没有股票，也不在冷冻期，说明在0位置就没有做任何决策。此时收益也是0 noStock[0] = 0;
　　针对一个普遍位置i// 如果i位置要处于冷冻期，那么前一个位置必须持有股票，且在当前位置卖掉，处于cooldown状态 cooldown[i] = withStock[i - 1] + arr[i]; // 如果i位置要持有股票，那么前一个位置可以持有股票，到当前位置不做决策，或者前一个位置没有股票，当前位置买入一股 withStock[i] = Math.max(withStock[i - 1], noStock[i - 1] - arr[i]); // 如果i位置没有股票，那么前一个位置可能也没股票，或者前一个位置是冷冻期，到当前位置也没有进行买入动作 noStock[i] = Math.max(noStock[i - 1], cooldown[i - 1]);
　　最大收益就是如上三种方式的最大值。完整代码见：public class LeetCode_0309_BestTimeToBuyAndSellStockWithCooldown {     public static int maxProfit(int[] arr) {         if (arr.length < 2) {             return 0;         }         int N = arr.length;         // 处于冷冻期         int[] cooldown = new int[N];         // 持有股票         int[] withStock = new int[N];         // 不持有股票，也不处于冷冻期         int[] noStock = new int[N];         cooldown[0] = 0;         withStock[0] = -arr[0];         noStock[0] = 0;         for (int i = 1; i < arr.length; i++) {             withStock[i] = Math.max(withStock[i - 1], noStock[i - 1] - arr[i]);             cooldown[i] = withStock[i - 1] + arr[i];             noStock[i] = Math.max(noStock[i - 1], cooldown[i - 1]);         }         return Math.max(cooldown[N - 1], Math.max(withStock[N - 1], noStock[N - 1]));     } }
　　由于三个数组有递推关系，所以可以用三个变量替换三个数组，做空间压缩，优化后的代码如下：public class LeetCode_0309_BestTimeToBuyAndSellStockWithCooldown {         // 空间压缩版本     public static int maxProfit(int[] arr) {         if (arr.length < 2) {             return 0;         }         // 处于冷冻期         int cooldown = 0;         // 持有股票         int withStock = -arr[0];         // 不持有股票，也不处于冷冻期         int noStock = 0;          for (int i = 1; i < arr.length; i++) {             int next1 = Math.max(withStock, noStock - arr[i]);             int next2 = withStock + arr[i];             int next3 = Math.max(noStock, cooldown);             withStock = next1;             cooldown = next2;             noStock = next3;         }         return Math.max(cooldown, Math.max(withStock, noStock));     } } LeetCode 714. 买卖股票的最佳时机含手续费#
　　主要思路：由于没有冷冻期，所以在i位置的时候，状态只有两种// withStock[i]表示：i位置有股票的状态下，最大收益 int[] withStock = new int[arr.length]; // noStock[i]表示：i位置没有股票的状态下，最大收益 int[] noStock = new int[arr.length];
　　针对0位置// 0位置持有股票，最大收益，只可能是0位置买入一股 withStock[0] = -arr[0]; // 0位置不持有股票，最大收益，只能是0位置不做交易，收益为0，如果0位置做交易，收益就是(0 - arr[i] + arr[i] - fee),显然小于0 noStock[0] = 0;
　　针对普遍位置i// i位置需要有股票，说明i位置的股票可以是i-1位置到现在不交易获得的，也可以是i-1位置没有股票，买下当前这一股获得的 withStock[i] = Math.max(withStock[i - 1], noStock[i - 1] - arr[i]); // i位置没有股票，说明i位置的股票可以由i-1位置上有股票的状态到当前位置卖出一股（含手续费），也可以是沿用上一个位置没有股票的最大收益 noStock[i] = Math.max(withStock[i - 1] + arr[i] - fee, noStock[i - 1]);
　　完整代码如下：public class LeetCode_0714_BestTimeToBuyAndSellStockWithTransactionFee {     public static int maxProfit1(int[] arr, int fee) {         if (arr.length < 2) {             return 0;         }         int[] withStock = new int[arr.length];         int[] noStock = new int[arr.length];         // 持有股票         withStock[0] = -arr[0];         // 不持有股票         noStock[0] = 0;         for (int i = 1; i < arr.length; i++) {             withStock[i] = Math.max(withStock[i - 1], noStock[i - 1] - arr[i]);             noStock[i] = Math.max(withStock[i - 1] + arr[i] - fee, noStock[i - 1]);         }         return Math.max(withStock[arr.length - 1], noStock[arr.length - 1]);     } }
　　同样的，两个数组都有递推关系，可以做空间压缩，简化后的代码如下：public class LeetCode_0714_BestTimeToBuyAndSellStockWithTransactionFee {      public static int maxProfit(int[] arr, int fee) {         if (arr.length < 2) {             return 0;         }         // 持有股票         int withStock = -arr[0];         // 不持有股票         int noStock = 0;         for (int i = 1; i < arr.length; i++) {             int next1 = Math.max(withStock, noStock - arr[i]);             int next3 = Math.max(withStock + arr[i] - fee, noStock);             withStock = next1;             noStock = next3;         }         return Math.max(withStock, noStock);     } }
　　原文链接：买卖股票的最佳时机系列问题 - Grey Zeng - 博客园