LeetCode之买卖股票问题

参考文章：

• 股票问题系列通解 (opens new window)
• 一个方法团灭Leetcode股票买卖问题 (opens new window)

一种常用的方法是将「买入」和「卖出」分开进行考虑：「买入」为负收益，而「卖出」为正收益。在初入股市时，你只有「买入」的权利，只能获得负收益。而当你「买入」之后，你就有了「卖出」的权利，可以获得正收益。显然，我们需要尽可能地降低负收益而提高正收益，因此我们的目标总是将收益值最大化。因此，我们可以使用动态规划的方法，维护在股市中每一天结束后可以获得的「累计最大收益」，并以此进行状态转移，得到最终的答案。

通用状态转移方程（详情请看参考文章）：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

base case：

dp[-1][...][0] = dp[...][0][0] = 0
dp[-1][...][1] = dp[...][0][1] = -prices[0]

买卖股票的最佳时机（只能一笔交易）

LC: 121.买卖股票的最佳时机 (opens new window)

给定一个数组，它的第i个元素是一支给定股票第i天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。注意：你不能在买入股票前卖出股票。

我们需要找出给定数组中两个数字之间的最大差值（即最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。

形式上，对于每组i和j（其中j > i）我们需要找出max(prices[j] − prices[i])。

• 方法一：暴力解法

  以当前价格买入，并比对后面所有卖出价格

  时空复杂度：O(n²) O(1)

  var maxProfit = function (prices) {
    let maxprofit = 0;
    for (let i = 0; i < prices.length - 1; i++) {
      for (let j = i + 1; j < prices.length; j++) {
        const profit = prices[j] - prices[i];
        if (profit > maxprofit) {
          maxprofit = profit;
        }
      }
    }
    return maxprofit;
  };
  

• 方法二：一次遍历

  假如计划在第i天卖出股票，那么最大利润的差值一定是在[0, i-1]之间选最低点买入；我们只要用一个变量记录一个历史最低价格minprice，我们就可以假设自己的股票是在那天买的。那么我们在第i天卖出股票能得到的利润就是prices[i] - minprice。因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

  时空复杂度：O(n) O(1)

  var maxProfit = function (prices) {
    let minPrice = Number.MAX_VALUE; // 最低的买入时机
    let maxprofit = 0;
    for (let i = 0; i < prices.length; i++) {
      if (prices[i] < minPrice) {
        minPrice = prices[i]; // 买入时机
      } else if (prices[i] - minPrice > maxprofit) {
        maxprofit = prices[i] - minPrice; // 卖出时机
      }
    }
    return maxprofit;
  };
  

• 方法三：通用动态规划

  var maxProfit = function (prices) {
    const n = prices.length;
    // const dp = Array.from({ length: n + 1 }, () => ([0, 0])); // [天数, 是否持有股票]
    // dp[0][0] = 0; // 开始时未持有股票收益为0
    // dp[0][1] = -prices[0]; // 开始时持有股票收益为负的第一个价格
    // for (let i = 1; i <= n; i++) {
    //   // 当前天没持有股票：前一天就没有或者是前一天有然后今天卖了
    //   dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
    //   // 当前天持有股票：前一天就持有或者今天买入
    //   dp[i][1] = Math.max(dp[i - 1][1], -prices[i - 1]);
    // }
    // return dp[n][0]; // 最后一天手里面未持有肯定比持有收益大
  
    // 空间优化 -- 每一天的状态只与前一天的状态有关
    let dp0 = 0;
    let dp1 = -prices[0]; // 前一天持有和未持有股票的收益
    for (const price of prices) {
      dp0 = Math.max(dp0, dp1 + price);
      dp1 = Math.max(dp1, -price);
    }
    return dp0;
  };
  

买卖股票的最佳时机（多笔交易）

LC: 122.买卖股票的最佳时机 (opens new window)

给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

• 方法一：动态规划

  var maxProfit = function (prices) {
    // const n = prices.length;
    // const dp = Array.from({ length: n + 1 }, () => ([0, 0]));
    // dp[0][0] = 0;
    // dp[0][1] = -prices[0];
    // for (let i = 1; i <= n; i++) {
    //   // 需要在前一天收益的基础上去进行买卖
    //   // 卖出要在前一天持有的收益上卖出
    //   dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
    //   // 买入也要在前一天未持有的收益上进行买入
    //   dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);
    // }
    // return dp[n][0];
  
    // 空间优化 -- 每一天的状态只与前一天的状态有关
    let dp0 = 0;
    let dp1 = -prices[0];
    for (const price of prices) {
      dp0 = Math.max(dp0, dp1 + price);
      dp1 = Math.max(dp1, dp0 - price);
    }
    return dp0;
  };
  

  时间复杂度：O(n)，其中n为数组的长度。一共有2n个状态，每次状态转移的时间复杂度为O(1)，因此时间复杂度为O(2n)=O(n)。 空间复杂度：O(n)。我们需要开辟O(n)空间存储动态规划中的所有状态。如果使用空间优化，空间复杂度可以优化至O(1)。

• 方法二：贪心

  由于股票的购买没有限制，因此整个问题等价于寻找x个不相交的区间 $(l_i,r_i]$ 使得如下的等式最大化

  $$\sum_{i=1}^{x} a[r_i]-a[l_i]$$

  其中 $l_i$ 表示在第 $l_i$ 天买入， $r_i$ 表示在第 $r_i$ 天卖出。

  同时我们注意到对于 $(l_i,r_i]$ 这一个区间贡献的价值 $a[r_i]-a[l_i]$，其实等价于 $(l_i,l_i+1],(l_i+1,l_i+2],\ldots,(r_i-1,r_i]$ 这若干个区间长度为 1 的区间的价值和，即

  $$a[r_i]-a[l_i]=(a[r_i]-a[r_i-1])+(a[r_i-1]-a[r_i-2])+\ldots+(a[l_i+1]-a[l_i])$$

  因此问题可以简化为找x个长度为 1 的区间 $(l_i,l_i+1]$ 使得 $\sum_{i=1}^{x} a[l_i+1]-a[l_i]$ 价值最大化。

  贪心的角度考虑我们每次选择贡献大于0的区间即能使得答案最大化，因此最后答案为

  $$\textit{ans}=\sum_{i=1}^{n-1}\max\{0,a[i]-a[i-1]\}$$

  其中n为数组的长度。

  需要说明的是，贪心算法只能用于计算最大利润，计算的过程并不是实际的交易过程。 考虑题目中的例子[1,2,3,4,5]，数组的长度n=5，由于对所有的1 ≤ i < n都有a[i] > a[i-1]，因此答案为

  $$\textit{ans}=\sum_{i=1}^{n-1}a[i]-a[i-1]=4$$

  但是实际的交易过程并不是进行4次买入和4次卖出，而是在第1天买入，第5天卖出。

  var maxProfit = function (prices) {
    let ans = 0;
    const n = prices.length;
    for (let i = 1; i < n; ++i) {
      ans += Math.max(0, prices[i] - prices[i - 1]);
    }
    return ans;
  };
  

  时间复杂度：O(n)，其中n为数组的长度。我们只需要遍历一次数组即可。 空间复杂度：O(1)。只需要常数空间存放若干变量。

• 方法三：峰谷法

  关键是我们需要考虑到紧跟谷的每一个峰值以最大化利润。如果我们试图跳过其中一个峰值来获取更多利润，那么我们最终将失去其中一笔交易中获得的利润，从而导致总利润的降低。

  时间复杂度：O(n)。遍历一次。 空间复杂度：O(1)。需要常量的空间。

  var maxProfit = function (prices) {
    let i = 0;
    let valley = prices[0];
    let peak = prices[0];
    let maxprofit = 0; // 最大利润
    while (i < prices.length - 1) {
      while (i < prices.length - 1 && prices[i] >= prices[i + 1]) i++;
      valley = prices[i]; // 找到一个波谷
      while (i < prices.length - 1 && prices[i] <= prices[i + 1]) i++;
      peak = prices[i]; // 找到波峰
      maxprofit += peak - valley;
    }
    return maxprofit;
  };
  

买卖股票的最佳时机（最多两笔交易）

LC: 123.买卖股票的最佳时机 (opens new window)

给定一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

• 方法一：动态规划

  由于我们最多可以完成两笔交易，因此在任意一天结束之后，我们会处于以下五个状态中的一种：

  • 未进行过任何操作；
  • 只进行过一次买操作；
  • 进行了一次买操作和一次卖操作，即完成了一笔交易；
  • 在完成了一笔交易的前提下，进行了第二次买操作；
  • 完成了全部两笔交易。

  由于第一个状态的利润显然为0，因此我们可以不用将其记录。对于剩下的四个状态，我们分别将它们的最大利润记为 $\textit{buy}_1$，$\textit{sell}_1$，$\textit{buy}_2$ 以及 $\textit{sell}_2$。 如果我们知道了第i−1天结束后的这四个状态，那么如何通过状态转移方程得到第i天结束后的这四个状态呢？

  对于 $\textit{buy}_1$ 而言，在第i天我们可以不进行任何操作，保持不变，也可以在未进行任何操作的前提下以prices[i]的价格买入股票，那么 $\textit{buy}_1$的状态转移方程即为：

  $$\textit{buy}_1 = \max \{ \textit{buy}_1', -\textit{prices}[i] \}$$

  这里我们用 $\textit{buy}_1'$ 表示第i-1天的状态，以便于和第i天的状态 $\textit{buy}_1$ 进行区分。 对于 $\textit{sell}_1$ 而言，在第i天我们可以不进行任何操作，保持不变，也可以在只进行过一次买操作的前提下以prices[i]的价格卖出股票，那么 $\textit{sell}_1$ 的状态转移方程即为：

  $$\textit{sell}_1 = \max \{ \textit{sell}_1', \textit{buy}_1' + \textit{prices}[i] \}$$

  同理我们可以得到 $\textit{buy}_2$ 和 $\textit{sell}_2$ 对应的状态转移方程：

  $$\begin{aligned} & \textit{buy}_2 = \max \{ \textit{buy}_2', \textit{sell}_1' - \textit{prices}[i] \} \\ & \textit{sell}_2 = \max \{ \textit{sell}_2', \textit{buy}_2' + \textit{prices}[i] \} \end{aligned}$$

  在考虑边界条件时，我们需要理解下面的这个事实：

  无论题目中是否允许「在同一天买入并且卖出」这一操作，最终的答案都不会受到影响，这是因为这一操作带来的收益为零。

  因此，在状态转移时，我们可以直接写成：

  $$\begin{cases} \textit{buy}_1 = \max \{ \textit{buy}_1, -\textit{prices}[i] \} \\ \textit{sell}_1 = \max \{ \textit{sell}_1, \textit{buy}_1 + \textit{prices}[i] \} \\ \textit{buy}_2 = \max \{ \textit{buy}_2, \textit{sell}_1 - \textit{prices}[i] \} \\ \textit{sell}_2 = \max \{ \textit{sell}_2, \textit{buy}_2 + \textit{prices}[i] \} \end{cases}$$

  例如在计算 $\textit{sell}_1$ 时，我们直接使用 $\textit{buy}_1$ 而不是 $\textit{buy}_1'$ 进行转移。$\textit{buy}_1$ 比 $\textit{buy}_1'$ 多考虑的是在第i天买入股票的情况，而转移到 $\textit{sell}_1$ 时，考虑的是在第i天卖出股票的情况，这样在同一天买入并且卖出收益为零，不会对答案产生影响。同理对于 $\textit{buy}_2$ 以及 $\textit{sell}_2$ ，我们同样可以直接根据第i天计算出的值来进行状态转移。

  那么对于边界条件，我们考虑第i=0天时的四个状态：$\textit{buy}_1$ 即为以prices[0]的价格买入股票，因此 $\textit{buy}_1$ = -prices[0]；$\textit{sell}_1$ 即为在同一天买入并且卖出，因此 $\textit{sell}_1$ = 0；$\textit{buy}_2$ 即为在同一天买入并且卖出后再以prices[0]的价格买入股票，因此 $\textit{buy}_2$ = -prices[0]；同理可得 $\textit{sell}_2$ = 0 。我们将这四个状态作为边界条件，从i=1开始进行动态规划，即可得到答案。

  在动态规划结束后，由于我们可以进行不超过两笔交易，因此最终的答案在0，$\textit{sell}_1$ ，$\textit{sell}_2$ 中，且为三者中的最大值。然而我们可以发现，由于在边界条件中 $\textit{sell}_1$ 和 $\textit{sell}_2$ 的值已经为0，并且在状态转移的过程中我们维护的是最大值，因此 $\textit{sell}_1$ 和 $\textit{sell}_2$ 最终一定大于等于0。同时，如果最优的情况对应的是恰好一笔交易，那么它也会因为我们在转移时允许在同一天买入并且卖出这一宽松的条件，从 $\textit{sell}_1$ 转移至 $\textit{sell}_2$ ，因此最终的答案即为 $\textit{sell}_2$ 。

  var maxProfit = function (prices) {
    const n = prices.length;
    const dp = Array.from({ length: n + 1 }, () => Array.from({ length: 3 }, () => ([0, 0])));
    const k = 2;
    // 第0天最多交易1次或2次手里分别持有或未持有股票的收益
    dp[0][1][0] = 0;
    dp[0][2][0] = 0;
    dp[0][1][1] = -prices[0];
    dp[0][2][1] = -prices[0];
    for (let i = 1; i <= n; i++) {
      for (let j = k; j >= 1; j--) { // 枚举最多k次交易
        dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1]);
        dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i - 1]);
      }
    }
    return dp[n][k][0];
  };
  

  空间优化版本：

  var maxProfit = function (prices) {
    const n = prices.length;
    let buy1 = -prices[0];
    let buy2 = -prices[0]; // 前一天最多1次或2次交易后且手里持有股票的收益
    let sell1 = 0;
    let sell2 = 0; // 前一天最多1次或2次交易后且手里未持有股票的收益
    for (let i = 1; i < n; i++) {
      // 最多一次交易且手里持有的收益为 "原来就交易一次并继续持有" 或者 "本次买入"
      buy1 = Math.max(buy1, -prices[i]);
      // 最多一次交易且手里未持有的收益为 "原来就交易一次买入后在本次卖出" 或者 "原来持有本次卖出"
      sell1 = Math.max(sell1, buy1 + prices[i]);
      // 最多两次交易且手里持有的收益为 "原来就交易两次并继续持有" 或者 "原来交易一次后手里为空本次买入"
      buy2 = Math.max(buy2, sell1 - prices[i]);
      // 最多两次交易且手里未持有的收益为 "原来就交易两次后手里为空" 或者 "原来交易两次手里持有在本次卖出"
      sell2 = Math.max(sell2, buy2 + prices[i]);
    }
    // 结果返回最多2次交易后手里未持有股票的收益
    return sell2;
  };
  

  时间复杂度：O(n)。 空间复杂度：O(1)。

买卖股票的最佳时机（最多K笔交易）

LC: 188.买卖股票的最佳时机 (opens new window)

给定一个整数数组prices，它的第i个元素prices[i]是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

与其余的股票问题类似，我们使用一系列变量存储「买入」的状态，再用一系列变量存储「卖出」的状态，通过动态规划的方法即可解决本题。

• 方法一：动态规划

  我们用buy[i][j]表示对于数组prices[0..i]中的价格而言，进行恰好j笔交易，并且当前手上持有一支股票，这种情况下的最大利润；用sell[i][j]表示恰好进行j笔交易，并且当前手上不持有股票，这种情况下的最大利润。

  那么我们可以对状态转移方程进行推导。对于buy[i][j]，我们考虑当前手上持有的股票是否是在第i天买入的。如果是第i天买入的，那么在第i-1天时，我们手上不持有股票，对应状态sell[i−1][j]，并且需要扣除prices[i]的买入花费；如果不是第i天买入的，那么在第i-1天时，我们手上持有股票，对应状态buy[i][j]。那么我们可以得到状态转移方程：

  $$buy[i][j] = max{ buy[i−1][j], sell[i−1][j] − price[i] }$$

  同理对于sell[i][j]，如果是第i天卖出的，那么在第i-1天时，我们手上持有股票，对应状态buy[i−1][j−1]，并且需要增加prices[i]的卖出收益；如果不是第i天卖出的，那么在第i-1天时，我们手上不持有股票，对应状态sell[i−1][j]。那么我们可以得到状态转移方程：

  $$sell[i][j] = max{ sell[i−1][j], buy[i−1][j−1] + price[i] }$$

  由于在所有的n天结束后，手上不持有股票对应的最大利润一定是严格由于手上持有股票对应的最大利润的，然而完成的交易数并不是越多越好（例如数组prices单调递减，我们不进行任何交易才是最优的），因此最终的答案即为sell[n−1][0..k]中的最大值。

  细节

  在上述的状态转移方程中，确定边界条件是非常重要的步骤。我们可以考虑将所有的buy[0][0..k]以及sell[0][0..k]设置为边界。 对于buy[0][0..k]，由于只有prices[0]唯一的股价，因此我们不可能进行过任何交易，那么我们可以将所有的buy[0][1..k]设置为一个非常小的值，表示不合法的状态。而对于buy[0][0]，它的值为−prices[0]，即「我们在第0天以prices[0]的价格买入股票」是唯一满足手上持有股票的方法。 对于sell[0][0..k]，同理我们可以将所有的sell[0][1..k]设置为一个非常小的值，表示不合法的状态。而对于sell[0][0]，它的值为0，即「我们在第0天不做任何事」是唯一满足手上不持有股票的方法。 在设置完边界之后，我们就可以使用二重循环，在i∈[1,n),j∈[0,k]的范围内进行状态转移。需要注意的是，sell[i][j]的状态转移方程中包含buy[i−1][j−1]，在j=0时其表示不合法的状态，因此在j=0时，我们无需对sell[i][j]进行转移，让其保持值为0即可。

  最后需要注意的是，本题中k的最大值可以达到$10^9$，然而这是毫无意义的，因为n天最多只能进行 $\lfloor \frac{n}{2} \rfloor$ 笔交易，其中 $\lfloor x \rfloor$ 表示对x向下取整。因此我们可以将k对 $\lfloor \frac{n}{2} \rfloor$ 取较小值之后再进行动态规划。

  var maxProfit = function (k, prices) {
    if (!prices.length) {
      return 0;
    }
    const n = prices.length;
    k = Math.min(k, Math.floor(n / 2));
    const buy = new Array(n).fill(0).map(() => new Array(k + 1).fill(0));
    const sell = new Array(n).fill(0).map(() => new Array(k + 1).fill(0));
    buy[0][0] = -prices[0];
    sell[0][0] = 0;
    for (let i = 1; i <= k; ++i) {
      buy[0][i] = sell[0][i] = -Number.MAX_VALUE;
    }
    for (let i = 1; i < n; ++i) {
      buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
      for (let j = 1; j <= k; ++j) {
        buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
        sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
      }
    }
    return Math.max(...sell[n - 1]);
  };
  

  注意到在状态转移方程中，buy[i][j]和sell[i][j]都从buy[i−1][..]以及sell[i−1][..]转移而来，因此我们可以使用一维数组而不是二维数组进行状态转移，即：

  $$\begin{cases} b[j] \leftarrow \max \big\{ b[j], s[j] - \textit{price}[i] \big\} \\ \\ s[j] \leftarrow \max \big\{ s[j], b[j-1] + \textit{price}[i] \big\} \end{cases}$$

  这样的状态转移方程会因为状态的覆盖而变得不同。例如如果我们先计算b而后计算s，那么在计算到s[j]时，其状态转移方程中包含的b[j−1]这一项的值已经被覆盖了，即本来应当是从二维表示中的buy[i−1][j−1]转移而来，而现在却变成了buy[i][j−1]。但其仍然是正确的。

  我们考虑buy[i][j−1]的状态转移方程：

  $$b[j-1] \leftarrow = \max \big\{ , \textit{sell}[i-1][j-1] - \textit{price}[i] \big\}$$

  那么s[j]s[j]的状态转移方程实际上为：

  $$s[j] \leftarrow \max \big\{ s[j], + \textit{prices}[i], \textit{sell}[i-1][j-1] \big\}$$

  为什么s[j]s[j]的状态转移方程中会出现sell[i−1][j−1]这一项？实际上，我们是把「在第i天以prices[i]的价格买入，并在同一天以prices[i]的价格卖出」看成了一笔交易，这样对应的收益即为：

  $$sell[i−1][j−1] − prices[i] + prices[i]$$

  也就是sell[i−1][j−1]本身。这种在同一天之内进行一笔交易的情况，收益为零，它并不会带来额外的收益，因此对最终的答案并不会产生影响，状态转移方程在本质上仍然是正确的。

  var maxProfit = function (k, prices) {
    if (!prices.length) {
      return 0;
    }
    const n = prices.length;
    k = Math.min(k, Math.floor(n / 2));
    const buy = new Array(k + 1).fill(0);
    const sell = new Array(k + 1).fill(0);
    [buy[0], sell[0]] = [-prices[0], 0];
    for (let i = 1; i < k + 1; ++i) {
      buy[i] = sell[i] = -Number.MAX_VALUE;
    }
    for (let i = 1; i < n; ++i) {
      buy[0] = Math.max(buy[0], sell[0] - prices[i]);
      for (let j = 1; j < k + 1; ++j) {
        buy[j] = Math.max(buy[j], sell[j] - prices[i]);
        sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);
      }
    }
    return Math.max(...sell);
  };
  

  时间复杂度：O(n min(n,k))，其中n是数组prices的大小，即我们使用二重循环进行动态规划需要的时间。 空间复杂度：O(n min(n,k)) 或 O(min(n,k))，取决于我们使用二维数组还是一维数组进行动态规划。

• 方法二：动态规划

  var maxProfit = function (k, prices) {
    const n = prices.length;
    const dp = Array.from({ length: n + 1 }, () => Array.from({ length: k + 1 }, () => ([0, 0])));
    for (let i = 0; i <= n; i++) {
      // 一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，
      // 如果超过，就没有约束作用了，相当于 k 没有限制的情况 可以直接使用第二题那种情形
      for (let j = k; j >= 1; j--) {
        if (i === 0) {
          dp[i][j][0] = 0;
          dp[i][j][1] = -prices[i];
        } else {
          dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1]);
          dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i - 1]);
        }
      }
    }
    return dp[n][k][0];
  };
  

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

LC: 309.最佳买卖股票时机含冷冻期 (opens new window)

给定一个整数数组，其中第i个元素代表了第i天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票（即冷冻期为1天）。

• 方法一：动态规划

  我们用f[i]表示第i天结束之后的「累计最大收益」。根据题目描述，由于我们最多只能同时买入（持有）一支股票，并且卖出股票后有冷冻期的限制，因此我们会有三种不同的状态：

  • 我们目前持有一支股票，对应的「累计最大收益」记为f[i][0]；
  • 我们目前不持有任何股票，并且处于冷冻期中，对应的「累计最大收益」记为f[i][1]；
  • 我们目前不持有任何股票，并且不处于冷冻期中，对应的「累计最大收益」记为f[i][2]。

  这里的「处于冷冻期」指的是在第i天结束之后的状态。也就是说：如果第i天结束之后处于冷冻期，那么第i+1天无法买入股票。

  如何进行状态转移呢？在第i天时，我们可以在不违反规则的前提下进行「买入」或者「卖出」操作，此时第i天的状态会从第i−1天的状态转移而来；我们也可以不进行任何操作，此时第i天的状态就等同于第i−1天的状态。那么我们分别对这三种状态进行分析：

  • 对于f[i][0]，我们目前持有的这一支股票可以是在第i−1天就已经持有的，对应的状态为f[i−1][0]；或者是第i天买入的，那么第i−1天就不能持有股票并且不处于冷冻期中，对应的状态为f[i−1][2]加上买入股票的负收益prices[i]。因此状态转移方程为：

  $$f[i][0]= max( f[i−1][0], f[i−1][2] − prices[i] )$$

  • 对于f[i][1]，我们在第i天结束之后处于冷冻期的原因是在当天卖出了股票，那么说明在第i-1天时我们必须持有一支股票，对应的状态为f[i−1][0]加上卖出股票的正收益prices[i]。因此状态转移方程为：

  $$f[i][1] = f[i−1][0] + prices[i]$$

  • 对于f[i][2]，我们在第i天结束之后不持有任何股票并且不处于冷冻期，说明当天没有进行任何操作，即第i-1天时不持有任何股票：如果处于冷冻期，对应的状态为f[i−1][1]；如果不处于冷冻期，对应的状态为f[i−1][2]。因此状态转移方程为：

  $$f[i][2]=max(f[i−1][1],f[i−1][2])$$

  这样我们就得到了所有的状态转移方程。如果一共有n天，那么最终的答案即为：

  $$max(f[n−1][0],f[n−1][1],f[n−1][2])$$

  注意到如果在最后一天（第n−1天）结束之后，手上仍然持有股票，那么显然是没有任何意义的。因此更加精确地，最终的答案实际上是f[n−1][1]和f[n−1][2]中的较大值，即：

  $$max(f[n−1][1],f[n−1][2])$$

  细节

  我们可以将第0天的情况作为动态规划中的边界条件：

  $$\begin{cases} f[0][0] &= -{\it prices}[0] \\ f[0][1] &= 0 \\ f[0][2] &= 0 \end{cases}$$

  在第0天时，如果持有股票，那么只能是在第0天买入的，对应负收益−prices[0]；如果不持有股票，那么收益为零。注意到第0天实际上是不存在处于冷冻期的情况的，但我们仍然可以将对应的状态f[0][1]置为零，这其中的原因留给读者进行思考。 这样我们就可以从第1天开始，根据上面的状态转移方程进行进行动态规划，直到计算出第n-1天的结果。

  为什么仍然可以将对应的状态f[0][1]置为零？

  f[0][1]只影响f[1][2]，而f[1][2]又是由f[0][1]和f[0][2]共同决定的，而f[0][2]的状态就是第0天不买入肯定就是0。因此f[1][2] = Math.max(f[0][1], f[0][2])，只要f[0][1] <= 0都是不会造成影响的。

  var maxProfit = function (prices) {
    if (prices.length === 0) {
      return 0;
    }
    const n = prices.length;
    // f[i][0]: 手上持有股票的最大收益
    // f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
    // f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
    const f = new Array(n).fill(0).map(() => new Array(3).fill(0));
    f[0][0] = -prices[0];
    for (let i = 1; i < n; ++i) {
      f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);
      f[i][1] = f[i - 1][0] + prices[i];
      f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]);
    }
    return Math.max(f[n - 1][1], f[n - 1][2]);
  };
  

  空间优化

  注意到上面的状态转移方程中，f[i][..]只与f[i−1][..]有关，而与f[i−2][..]及之前的所有状态都无关，因此我们不必存储这些无关的状态。也就是说，我们只需要将f[i−1][0]，f[i−1][1]，f[i−1][2]存放在三个变量中，通过它们计算出f[i][0]，f[i][1]，f[i][2]并存回对应的变量，以便于第i+1天的状态转移即可。

  var maxProfit = function (prices) {
    if (prices.length === 0) {
      return 0;
    }
    const n = prices.length;
    let f0 = -prices[0];
    let f1 = 0;
    let f2 = 0;
    for (let i = 1; i < n; ++i) {
      const newf0 = Math.max(f0, f2 - prices[i]);
      const newf1 = f0 + prices[i];
      const newf2 = Math.max(f1, f2);
      f0 = newf0;
      f1 = newf1;
      f2 = newf2;
    }
    return Math.max(f1, f2);
  };
  

• 方法二：通用公式动态规划

  var maxProfit = function (prices) {
    const n = prices.length;
    const dp = Array.from({ length: n + 1 }, () => ([0, 0]));
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for (let i = 1; i <= n; i++) {
      dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
      // 只有买入才有冷冻期限制 第一天可以直接买入
      // 如果天数大于等于2 那么买入的收益应该是往前两天的基础上计算
      dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2 < 0 ? 0 : i - 2][0] - prices[i - 1]);
    }
    return dp[n][0];
  };
  

  空间优化版本

  var maxProfit = function (prices) {
    const n = prices.length;
    // 前一天未持有 前两天未持有 前一天持有
    let dp0 = 0;
    let dp1 = 0;
    let dp2 = -prices[0];
    for (const price of prices) {
      const temp = dp0; // 暂存前一天未持有的收益
      dp0 = Math.max(dp0, dp2 + price);
      dp2 = Math.max(dp2, dp1 - price);
      dp1 = temp;
    }
    return dp0;
  };
  

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

LC: 714.买卖股票的最佳时机含手续费 (opens new window)

给定一个整数数组prices，其中第i个元素代表了第i天的股票价格；非负整数fee代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

• 方法一：动态规划

  考虑到「不能同时参与多笔交易」，因此每天交易结束后只可能存在手里有一支股票或者没有股票的状态。

  定义状态dp[i][0]表示第i天交易完后手里没有股票的最大利润，dp[i][1]表示第i天交易完后手里持有一支股票的最大利润（i从0开始）。 考虑dp[i][0]的转移方程，如果这一天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票，即dp[i−1][0]，或者前一天结束的时候手里持有一支股票，即dp[i−1][1]，这时候我们要将其卖出，并获得prices[i]的收益，但需要支付fee的手续费。因此为了收益最大化，我们列出如下的转移方程：

  $$dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]−fee}$$

  再来按照同样的方式考虑dp[i][1]按状态转移，那么可能的转移状态为前一天已经持有一支股票，即dp[i−1][1]，或者前一天结束时还没有股票，即dp[i−1][0]，这时候我们要将其买入，并减少prices[i]的收益。可以列出如下的转移方程：

  $$dp[i][1]=max{dp[i−1][1],dp[i−1][0]−prices[i]}$$

  对于初始状态，根据状态定义我们可以知道第0天交易结束的时候有dp[0][0] = 0以及dp[0][1] = −prices[0]。

  因此，我们只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候dp[n−1][0]的收益必然是大于dp[n−1][1]的，最后的答案即为dp[n−1][0]。

  var maxProfit = function (prices, fee) {
    const n = prices.length;
    const dp = new Array(n).fill(0).map((v) => new Array(2).fill(0));
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for (let i = 1; i < n; ++i) {
      dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
      dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[n - 1][0];
  };
  

  空间优化版本

  var maxProfit = function (prices, fee) {
    let dp0 = 0;
    let dp1 = -prices[0];
    for (const price of prices) {
      dp0 = Math.max(dp0, dp1 + price - fee);
      dp1 = Math.max(dp1, dp0 - price);
    }
    return dp0;
  };
  

  时间复杂度：O(n)，其中n为数组的长度。一共有2n个状态，每次状态转移的时间复杂度为O(1)，因此时间复杂度为O(2n)=O(n)。 空间复杂度：O(n)或O(1)，取决于是否使用数组存储所有的状态（滚动数组）。

• 方法二：贪心算法

  方法一中，我们将手续费放在卖出时进行计算。如果我们换一个角度考虑，将手续费放在买入时进行计算，那么就可以得到一种基于贪心的方法。

  我们用buy表示在最大化收益的前提下，如果我们手上拥有一支股票，那么它的最低买入价格是多少。在初始时，buy的值为prices[0]，加上手续费fee。那么当我们遍历到第i(i>0)天时：

  如果当前的股票价格prices[i]加上手续费fee小于buy，那么与其使用buy的价格购买股票，我们不如以prices[i] + fee的价格购买股票，因此我们将buy更新为prices[i] + fee；

  如果当前的股票价格prices[i]大于buy，那么我们直接卖出股票并且获得prices[i] − buy的收益。但实际上，我们此时卖出股票可能并不是全局最优的（例如下一天股票价格继续上升），因此我们可以提供一个反悔操作， 看成当前手上拥有一支买入价格为prices[i]的股票，将buy更新为prices[i]。这样一来，如果下一天股票价格继续上升，我们会获得prices[i+1] − prices[i]的收益，加上这一天prices[i] − buy的收益，恰好就等于在这一天不进行任何操作，而在下一天卖出股票的收益；

  对于其余的情况，prices[i]落在区间[buy−fee, buy]内，它的价格没有低到我们放弃手上的股票去选择它，也没有高到我们可以通过卖出获得收益，因此我们不进行任何操作。

  上面的贪心思想可以浓缩成一句话，即当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利。

  在遍历完整个数组prices之后之后，我们就得到了最大的总收益。

  var maxProfit = function (prices, fee) {
    const n = prices.length;
    let buy = prices[0] + fee;
    let profit = 0;
    for (let i = 1; i < n; i++) {
      if (prices[i] + fee < buy) {
        buy = prices[i] + fee;
      } else if (prices[i] > buy) {
        profit += prices[i] - buy;
        buy = prices[i];
      }
    }
    return profit;
  };
  

  • 时间复杂度：O(n)，其中n为数组的长度。
  • 空间复杂度：O(1)。

所有限制融为一体

输入股票价格数组prices，你最多进行k次交易，每次交易需要额外消耗fee的手续费，而且每次交易之后需要经过cooldown天的冷冻期才能进行下一次交易，请你计算并返回可以获得的最大利润。

/**
 * @description 股票求最大收益，含手续费、冷冻期、交易次数限制
 * @author fengchunqi
 * @date 2022-03-10 17:06:21
 * @param {number} k 最大交易次数
 * @param {number[]} prices 每日股票价格
 * @param {number} cooldown 冷冻期
 * @param {number} fee 交易手续费
 */
var maxProfitAllinone = function (k, prices, cooldown, fee) {
  const n = prices.length;
  const dp = Array.from({ length: n + 1 }, () => Array.from({ length: k + 1 }, () => ([0, 0])));
  for (let i = 0; i <= n; i++) {
    for (let j = k; j >= 1; j--) {
      if (i === 0) {
        dp[i][j][0] = 0;
        dp[i][j][1] = -prices[0];
      } else {
        dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1] - fee);
        dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - cooldown - 1 < 0 ? 0 : i - cooldown - 1][j - 1][0] - prices[i - 1]);
      }
    }
  }
  return dp[n][k][0];
};