股票问题是经典DP题，主要买入和卖出来获取最大利润。

121. 买卖股票的最佳时机

题目描述

image.png

解题思路

暴力法

C++

  1. int maxProfit(vector<int>& prices) {
  2.     int result = 0;
  3.     for (int i = 0; i < prices.size(); i++) {
  4.         for (int j = i + 1; j < prices.size(); j++){
  5.             result = max(result, prices[j] - prices[i]);
  6.         }
  7.     }
  8.     return result;
  9. }

贪心

选出最大和最小的相减，就是最大利润。

  1. /**
  2.          * 贪心算法
  3.          *
  4.          * @param prices
  5.          * @return
  6.          */
  7. public int maxProfit(int[] prices) {
  8.     int low = Integer.MAX_VALUE;
  9.     int result = 0;
  10.     for (int i = 0; i < prices.length; i++) {
  11.         low = Math.min(low, prices[i]); // 获取最小的左区间
  12.         result = Math.max(result, prices[i] - low); // 获取最大的利润
  13.     }
  15.     return result;
  16. }

DP

  • dp含义

dp[i][0] 表示第i天持有股票所得最多现金 ，dp[i][1] 表示第i天不持有股票所得最多现金。
注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态。

  • 递推公式

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

  • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
  • 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]

那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);
特别注意这里只能买入和卖出一次，所以递推公式不是上一次卖出价格减买入价格。所以不是dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]-prices[i]);
如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来

  • 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
  • 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

  • 初始化

那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -= prices[0];
dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;

  • 确定遍历顺序

从递推公式可以看出dp[i]都是有dp[i - 1]推导出来的，那么一定是从前向后遍历。

  • 举例推导dp数组

以示例1，输入：[7,1,5,3,6,4]为例，dp数组状态如下：
image.png
dp[5][1]就是结果，因为卖出一定比买入利润多。

  1. /**
  2.          * 动态规划
  3.          *
  4.          * @param prices
  5.          * @return
  6.          */
  7. public int maxProfit(int[] prices) {
  8.     if (prices.length == 0) {
  9.         return 0;
  10.     }
  12.     // dp[i][0] 表示第i天持有股票所得最多现金(持有股票 = 已买股票 + 买入股票)
  13.     // dp[i][1] 表示第i天不持有股票所得最多现金(不持有股票 = 没有购买股票 + 售出股票)
  14.     int[][] dp = new int[prices.length][2];
  15.     dp[0][0] -= prices[0];  // 此时第0天不能持有股票，只能买入股票
  16.     dp[0][1] = 0;   // 不持有股票现金就是0
  18.     for (int i = 1; i < prices.length; i++) {
  19.         //如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
  20.         //第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
  21.         //第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
  22.         //那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);
  23.         //如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来
  24.         //第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
  25.         //第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]
  26.         //同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
  27.         dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
  28.         dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
  29.     }
  31.     return dp[prices.length - 1][1];    // 最后一个不持有股票的现金一定比持有股票的多
  32. }

优化写法

  1. /**
  2.          * 优化为 2 × 2 的数组，递推公式都是由上一个推出来的，所以可以优化
  3.          *
  4.          * @param prices
  5.          * @return
  6.          */
  7. public int maxProfit(int[] prices) {
  8.     if (prices.length == 0) {
  9.         return 0;
  10.     }
  12.     // dp[i][0] 表示第i天持有股票所得最多现金(持有股票 = 已买股票 + 买入股票)
  13.     // dp[i][1] 表示第i天不持有股票所得最多现金(不持有股票 = 没有购买股票 + 售出股票)
  14.     int[][] dp = new int[2][2];
  15.     dp[0][0] -= prices[0];  // 此时第0天不能持有股票，只能买入股票
  16.     dp[0][1] = 0;   // 不持有股票现金就是0
  18.     for (int i = 1; i < prices.length; i++) {
  19.         //如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
  20.         //第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
  21.         //第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
  22.         //那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);
  23.         //如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来
  24.         //第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
  25.         //第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]
  26.         //同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
  27.         dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], -prices[i]);
  28.         dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);
  29.     }
  31.     return dp[prices.length % 2][1];    // 最后一个不持有股票的现金一定比持有股票的多
  32. }

122. 买卖股票的最佳时机 II

题目描述

image.png

解题思路

DP

本题和上一题的最大区别就是可以多次买入，所以和上一题只有递推公式不一样。
dp数组的含义：

  • dp[i][0] 表示第i天持有股票所得现金。
  • dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

  • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]

  • 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]（注意这里可以多次买入和卖出，所以买入的时候需要根据卖出的推出，所持有的现金可能有之前买卖过的利润。而不是-price[i]） ```cpp /**

    1.    * 动态规划
    2.    *
    3.    * @param prices
    4.    * @return
    5.    */

    public int maxProfit(int[] prices) { if (prices.length == 0) {

    1.   return 0;

    } int[][] dp = new int[prices.length][2]; dp[0][0] -= prices[0]; dp[0][1] = 0;

    for (int i = 1; i < prices.length; i++) {

    1.   // 与买卖股票I不同的是，现在是多次购买，所以买入股票是上一次未持有的现金减去买股票的钱（必须卖出才能买入）
    2.   dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
    3.   dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);

    }

    return dp[prices.length - 1][1]; }

  2. 优化
  4. ```cpp
  5. /**
  6.          * 动态规划（优化为 2 × 2 的数组）
  7.          *
  8.          * @param prices
  9.          * @return
  10.          */
  11. public int maxProfit(int[] prices) {
  12.     if (prices.length == 0) {
  13.         return 0;
  14.     }
  15.     int[][] dp = new int[prices.length][2];
  16.     dp[0][0] -= prices[0];
  17.     dp[0][1] = 0;
  19.     for (int i = 1; i < prices.length; i++) {
  20.         // 与买卖股票I不同的是，现在是多次购买，所以买入股票是上一次未持有的现金减去买股票的钱（必须卖出才能买入）
  21.         dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
  22.         dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);
  23.     }
  25.     return dp[(prices.length - 1) % 2][1];
  26. }

贪心

🔗

  1. /**
  2.          * 贪心算法
  3.          *
  4.          * @param prices
  5.          * @return
  6.          */
  7. public int maxProfit(int[] prices) {
  8.     int result = 0;
  9.     for (int i = 1; i < prices.length; i++) {
  10.         int profits = prices[i] - prices[i - 1];
  11.         // 贪心贪的地方：只计算利润为正的两张股票
  12.         if (profits > 0) {
  13.             result += profits;
  14.         }
  15.     }
  16.     return result;
  17. }

123. 买卖股票的最佳时机 III

题目描述

image.png

解题思路

本题和上一题II题的区别就是买卖次数，关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

  • 确定dp数组以及下标的含义

一天一共就有五个状态，

  1. 没有操作
  2. 第一次买入
  3. 第一次卖出
  4. 第二次买入
  5. 第二次卖出

    dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

  • 递推公式

需要注意：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票。
达到dp[i][1]状态，有两个具体操作：

  • 操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
  • 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]

那么dp[i][1]究竟选 dp[i-1][0] - prices[i]，还是dp[i - 1][1]呢？
一定是选最大的，所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
同理dp[i][2]也有两个操作：

  • 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
  • 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
同理第二次买卖股票的dp也可以推出。

  • 初始化

第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;
第0天做第一次买入的操作，dp[0][1] = -prices[0];
第0天做第一次卖出的操作，这个初始值应该是多少呢？
首先卖出的操作一定是收获利润，整个股票买卖最差情况也就是没有盈利即全程无操作现金为0，
从递推公式中可以看出每次是取最大值，那么既然是收获利润如果比0还小了就没有必要收获这个利润了。
所以dp[0][2] = 0;
第二次买入依赖于第一次卖出的状态，相当于第一次买入又卖出，进行第二次买入，所以初始化为-prices[0]，同理第二次卖出初始化为0。

  • 遍历顺序

根据递推公式可得，从前向后遍历。

  • 举例推导dp数组

以输入[1,2,3,4,5]为例
image.png
卖出的利润一定大于买入的利润，所以最大为dp[4][4]。

  1. public int maxProfit(int[] prices) {
  2.     if (prices.length == 0) {
  3.         return 0;
  4.     }
  5.     //            一天一共就有五个状态，
  6.     //            0：没有操作
  7.     //            1：第一次买入
  8.     //            2：第一次卖出
  9.     //            3：第二次买入
  10.     //            4：第二次卖出
  11.     //            dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
  12.     int[][] dp = new int[prices.length][5];
  13.     dp[0][0] = 0;   // 第0天没有操作
  14.     dp[0][1] -= prices[0];   // 第0天第一次买入股票
  15.     dp[0][2] = 0;   // 第0天第一次卖出股票
  16.     dp[0][3] -= prices[0];   // 第0天第二次买入股票
  17.     dp[0][4] = 0;   // 第0天第二次卖出股票
  19.     for (int i = 1; i < prices.length; i++) {
  20.         dp[i][0] = dp[i - 1][0];
  21.         dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);    // 第一次买入股票的现金，是由没有操作推出来的
  22.         dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
  23.         dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);    // 第二次买入股票的现金，是由第一次卖出股票推出来的
  24.         dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
  25.     }
  27.     return dp[prices.length - 1][4];  // 第二次卖出股票才是最大利润
  28. }

188. 买卖股票的最佳时机 IV

题目描述

image.png

解题思路

本题的思路和上一题相差不大，可以买入多次，而本题的多次需要根据k来推出多少次，所以可以根据上面3题的规律推出，奇数表示买入，偶数表示卖出。

  • dp数组的含义

使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]
j的状态表示为：

  • 0 表示不操作
  • 1 第一次买入
  • 2 第一次卖出
  • 3 第二次买入
  • 4 第二次卖出
  • …..

j的范围就定义为 2 * k + 1 就可以了。

  • 递推公式

递推公式和上一题基本一样，买入和卖出需要上一次的状态推出，只是多次循环递推dp数组而已。

  • 初始化

初始化和上一题一样的思路，所以可以将所以奇数初始化为-prices[0]，表示买入，所有偶数初始化为0，表示卖出。
遍历顺序根据递推公式可知道，从前向后遍历。

  • 举例推导dp数组

以输入[1,2,3,4,5]，k=2为例。
image.png
最后一次卖出，一定是利润最大的，dp[prices.size() - 1][2 * k]即红色部分就是最后求解。

  1. public int maxProfit(int k, int[] prices) {
  2.     if (prices.length == 0) {
  3.         return 0;
  4.     }
  6.     // dp[][0] 表示无操作
  7.     // dp[][偶数] 表示买入股票
  8.     // dp[][奇数] 表示卖出股票
  9.     int[][] dp = new int[prices.length][2 * k + 1];
  10.     // 初始化每次买入股票的现金
  11.     for (int i = 1; i < 2 * k; i += 2) {
  12.         dp[0][i] -= prices[0];
  13.     }
  15.     for (int i = 1; i < prices.length; i++) {
  16.         for (int j = 0; j < 2 * k - 1; j += 2) {
  17.             dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
  18.             dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
  19.         }
  20.     }
  22.     return dp[prices.length - 1][2 * k];
  23. }

309. 最佳买卖股票时机含冷冻期

题目描述

image.png

解题思路

本题和上一题的区别就是状态有所不同。

  • 确定dp数组以及下标的含义

dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。
其实本题很多同学搞的比较懵，是因为出现冷冻期之后，状态其实是比较复杂度，例如今天买入股票、今天卖出股票、今天是冷冻期，都是不能操作股票的。 具体可以区分出如下四个状态：

  • 状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
  • 卖出股票状态，这里就有两种卖出股票状态
    • 状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
    • 状态三：今天卖出了股票
  • 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

    也可以将状态四和状态二合并，但不太清楚。

  • 确定递推公式

达到买入股票状态（状态一）即：dp[i][0]，有两个具体操作：

  • 操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
  • 操作二：今天买入了，有两种情况
    • 前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
    • 前一天是保持卖出股票状态（状态二），dp[i - 1][1] - prices[i]

所以操作二取最大值，即：max(dp[i - 1][3], dp[i - 1][1]) - prices[i]
那么dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
达到保持卖出股票状态（状态二）即：dp[i][1]，有两个具体操作：

  • 操作一：前一天就是状态二
  • 操作二：前一天是冷冻期（状态四）

dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：

  • 操作一：昨天一定是买入股票状态（状态一），今天卖出

即：dp[i][2] = dp[i - 1][0] + prices[i];
达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：

  • 操作一：昨天卖出了股票（状态三）

dp[i][3] = dp[i - 1][2];

  • 初始化

这里主要讨论一下第0天如何初始化。
如果是持有股票状态（状态一）那么：dp[0][0] = -prices[0]，买入股票所剩现金为负数。
保持卖出股票状态（状态二），第0天没有卖出dp[0][1]初始化为0就行，
今天卖出了股票（状态三），同样dp[0][2]初始化为0，因为最少收益就是0，绝不会是负数。
同理dp[0][3]也初始为0。

  • 确定遍历顺序

从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历。

  • 举例推导dp数组

以 [1,2,3,0,2] 为例，dp数组如下：
image.png

最后结果是取 状态二，状态三，和状态四的最大值，不少同学会把状态四忘了，状态四是冷冻期，最后一天如果是冷冻期也可能是最大值。

个人的思考，如果冷冻期不知一天，而是2天，3天…，那么就可以多定义一个状态，表示第一天冷冻期还是第二天冷冻期。

  1. public int maxProfit(int[] prices) {
  2.     // 分为4个状态
  3.     //            状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
  4.     //            卖出股票状态，这里就有两种卖出股票状态
  5.     //              状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
  6.     //              状态三：今天卖出了股票
  7.     //            状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
  9.     //            dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。
  10.     int[][] dp = new int[prices.length][4];
  11.     dp[0][0] -= prices[0];  // 今天买入的话
  12.     dp[0][1] = 0;   // 第0天没有卖出
  13.     dp[0][2] = 0;   // 第0天卖出股票，也是相当于买入卖出，而且最小的利润是0，所以初始化为0
  14.     dp[0][3] = 0;   // 第0天没有卖出，也就没有冷冻期
  16.     for (int i = 1; i < prices.length; i++) {
  17.         // 持有股票有2个操作：(都取最大的利润)
  18.         //      操作一：昨天就是持有股票的状态，也就是昨天才买入(状态一)
  19.         //      操作二：1.昨天已经卖出股票很多天了，几天可以买入(状态二) 2.昨天时冷冻期，但今天可以买入(状态四)
  20.         dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i]));
  21.         //  卖出股票状态：(都去最大利润)
  22.         //      操作一：昨天就是卖出股票的状态(状态二)
  23.         //      操作二：左键就是冷冻期(状态四)
  24.         dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
  25.         // 今天正好卖出股票：也就是昨天刚买入，今天才能卖出
  26.         dp[i][2] = dp[i - 1][0] + prices[i];
  27.         // 冷冻期状态：昨天才卖出，今天才是冷冻期
  28.         dp[i][3] = dp[i - 1][2];
  29.     }
  31.     // 在冷冻期，卖出股票状态，正好卖出状态取最大的利润
  32.     return Math.max(dp[prices.length - 1][1], Math.max(dp[prices.length - 1][2], dp[prices.length - 1][3]));
  33. }

714. 买卖股票的最佳时机含手续费

题目描述

image.png

解题思路

dp

本题的思路和买卖股票III相差不大，只是多了一个手续费，只有递推公式有点区别！！！
这里重申一下dp数组的含义：
dp[i][0] 表示第i天持有股票所省最多现金。 dp[i][1] 表示第i天不持有股票所得最多现金
如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

  • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
  • 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]

所以：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
在来看看如果第i天不持有股票即dp[i][1]的情况， 依然可以由两个状态推出来

  • 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
  • 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金，注意这里需要有手续费了即：dp[i - 1][0] + prices[i] - fee

所以：dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);

此时为什么在卖出的时候相减呢？ 注意此时相减了之后取得是买入和卖出以及减去手续费的最大值，来判断值不值得卖出。

  1. public int maxProfit(int[] prices, int fee) {
  2.     int minPrice = prices[0];
  3.     int result = 0;
  4.     for (int i = 0; i < prices.length; i++) {
  5.         // 情况二，相当于买入
  6.         if (prices[i] < minPrice) minPrice = prices[i];
  7.         // 情况三：不作操作，保持原有状态（买入，卖出，不买不卖），卖出就亏了
  8.         if (prices[i] < minPrice || prices[i] < minPrice + fee) continue;
  9.         // 情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
  10.         if (prices[i] > minPrice + fee) {
  11.             result += prices[i] - minPrice - fee;
  12.             // 注意此时需要更新买入的值
  13.             minPrice = prices[i] - fee;
  14.         }
  15.     }
  17.     return result;
  18. }

贪心

链接🔗

  1. // 贪心法
  2. //        情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
  3. //        情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
  4. //        情况三：不作操作，保持原有状态（买入，卖出，不买不卖）
  5. public int maxProfit(int[] prices, int fee) {
  6.     int result = 0;
  7.     int minPrice = prices[0];
  8.     for (int i = 0; i < prices.length; i++) {
  9.         // 情况二：相当于买入
  10.         if (prices[i] < minPrice) {
  11.             minPrice = prices[i];
  12.         }
  14.         // 情况三：保持原有状态（因为此时买则不便宜，卖则亏本）
  15.         if (prices[i] > minPrice && prices[i] < (minPrice + fee)) {
  16.             continue;
  17.         }
  19.         // 计算利润，可能有多次计算利润，最后一次计算利润才是真正意义的卖出
  20.         if (prices[i] > minPrice + fee) {
  21.             result += prices[i] - minPrice - fee;   // 计算利润，如果后边有更赚的，就加上
  22.             minPrice = prices[i] - fee; // 情况一，这一步很关键，将买入的价格重新赋值
  23.         }
  24.     }
  25.     return result;
  27.     int result = 0;
  28.     int minPrice = Integer.MAX_VALUE;
  29.     for (int i = 0; i < prices.length; i++) {
  30.         if (prices[i] < minPrice) {
  31.             minPrice = prices[i];
  32.         }
  34.         if (prices[i] < minPrice || prices[i] < (minPrice + fee)) {
  35.             continue;
  36.         }
  38.         if (prices[i] > (minPrice + fee)) {
  39.             result += prices[i] - minPrice - fee;
  40.             minPrice = prices[i] - fee;
  41.         }
  43.     }
  44.     return result;
  45. }