题目

题目来源：力扣（LeetCode）

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。


示例 1:

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

思路分析

方法一：动态规划

1、定义状态

由于「不能同时参与多笔交易」，因此每天交易结束后只可能存在两种状态：

  • 手里有一支股票
  • 手里没有股票

定义二维数组 dp[in][2]

  • dp[i][0] 表示第 i 天手里没有股票可获得的最大利润 (i 从 0 开始)
  • dp[i][1] 表示第 i 天手里持有一支股票可获得的最大利润 (i 从 0 开始)

2、状态转移方程

  • 不持有股票：dp[i][0] = max(dp[i -1][0], dp[i - 1][1] + prices[i])

对于今天 (第 i 天) 不持有股票可获得的最大利润，可以从两个状态转移过来：

  • 昨天 (第 i - 1天) 也不持有，利润为 dp[i -1][0]
  • 昨天 (第 i - 1天) 持有，但今天 (第 i 天) 卖出了， 利润为 dp[i - 1][1] + prices[i]

两者取较大值

  • 持有股票：dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

对于今天持有股票可获取的最大利润，可以从两个状态转移过来：

  • 昨天也持有，利润为 dp[i - 1][1]
  • 昨天不持有，但今天买入了，利润为 dp[i - 1][0] - prices[i]

两者取较大值

3、状态初始值
对于第 0 天：
不持有股票，可获得利润为 0，即 dp[0][0] = 0
持有股票 (即花了 prices[0] 的钱买入，那么利润为负)，即 dp[0][1] = -prices[0]

4、确定输出值

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

代码实现

  1. /**
  2.  * @param {number[]} prices
  3.  * @return {number}
  4.  */
  5. var maxProfit = function (prices) {
  6.   const n = prices.length;
  7.   // 定义二维数组
  8.   const dp = new Array(n).fill(0).map(v => new Array(2).fill(0));
  9.   // 第 0 天不持有股票的利润
  10.   dp[0][0] = 0;
  11.   // 第 0 天持有股票的利润
  12.   dp[0][1] = -prices[0];
  13.   for (let i = 1; i < n; ++i) {
  14.     // 不持有股票可获得的最大利润
  15.     dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
  16.     // 持有股票可获得的最大利润
  17.     dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
  18.   }
  19.   // 部交易结束后，持有股票的收益一定低于不持有股票的收益，
  20.   // 因此这时候 dp[n - 1][0] 的收益必然是大于 dp[n - 1][1] 的，
  21.   // 最后的答案即为 dp[n - 1][0]
  22.   return dp[n - 1][0];
  23. };

空间优化

在上面的状态转移方程中，每一天的状态只与前一天的状态有关，而与更早的状态都无关，因此我们不必存储这些无关的状态，只需要将 dp[i - 1][0] 和 dp[i - 1][1] 存放在两个变量中，通过它们计算出 dp[i][0] 和 dp[i][1] 并存回对应的变量，以便于第 i + 1天的状态转移即可

  1. /**
  2.  * @param {number[]} prices
  3.  * @return {number}
  4.  */
  5. var maxProfit = function (prices) {
  6.   const n = prices.length;
  7.   // 第 0 天不持有股票的利润
  8.   let dp0 = 0;
  9.   // 第 0 天持有股票的利润
  10.   let dp1 = -prices[0];
  11.   for (let i = 1; i < n; ++i) {
  12.     // 不持有股票可获得的最大利润
  13.     let newDp0 = Math.max(dp0, dp1 + prices[i]);
  14.     // 持有股票可获得的最大利润
  15.     let newDp1 = Math.max(dp1, dp0 - prices[i]);
  16.     dp0 = newDp0;
  17.     dp1 = newDp1;
  18.   }
  19.   // 部交易结束后，持有股票的收益一定低于不持有股票的收益，
  20.   // 因此这时候 dp[n - 1][0] 的收益必然是大于 dp[n - 1][1] 的，
  21.   // 最后的答案即为 dp[n - 1][0]
  22.   return dp0;
  23. };

方法二：贪心算法

股票买卖策略：

  • 单独交易日： 设今天价格P1，明天价格P2，则今天买入、明天卖出可赚取金额 p2 - p1 (负值代表亏损)
  • 连续上涨交易日： 设此上涨交易日股票价格分别为 P1, P2, … , P5，则第一天买入最后一天卖出收益最大，即 Pn - P1 ；等价于每天都买卖，即 Pn - P1 = (P5 - P4) + … + (P3 - Pc2) + (P2 - P1)
  • 连续下降交易日： 则不买卖收益最大，即不会亏钱。

算法流程：

  • 遍历整个股票交易日价格列表 price，策略是所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）。
  1. 设 tmp 为第 i - 1 日买入与第 i 日卖出赚取的利润，即 tmp = prices[i] - prices[i - 1] ；
  2. 当该天利润为正 tmp > 0，则将利润加入总利润 ans；当利润为 0 或为负，则直接跳过；
  3. 遍历完成后，返回总利润 ans 。

代码实现：

  1. /**
  2.  * @param {number[]} prices
  3.  * @return {number}
  4.  */
  5. var maxProfit = function (prices) {
  6.   let ans = 0;
  7.   // 遍历整个股票交易日价格列表 price，
  8.   // 策略是所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）
  9.   for (let i = 1; i < prices.length; i++) {
  10.     // 当该天利润为正 prices[i] - prices[i - 1] > 0，
  11.     // 则将利润加入总利润 ans；当利润为 0 或为负，则直接跳过
  12.     if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
  13.   }
  14.   return ans;
  15. };

参考阅读： https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/jian-dan-dpmiao-dong-gu-piao-mai-mai-by-uc68p/ https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/ https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/best-time-to-buy-and-sell-stock-ii-zhuan-hua-fa-ji/ https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-by-liweiwei1419-2/