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

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

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

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

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

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

示例 1:

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

示例 4：

输入：prices = [1]
输出：0

提示：

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁵

思路分析

针对一个方法团灭 6 道股票问题 - 最佳买卖股票时机含冷冻期 - 力扣（LeetCode）这个解题框架，进行小试牛刀。

经过试验，将交易分成两步来计算，代码无法通过全部测试用例。只需要在买入或者卖出更新交易次数即可。

思考题：将表格改成变量时，还需要再思考思考。

一刷
二刷
三刷(暴力破解)
三刷(备忘录)
三刷(动态规划)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Runtime: 2 ms, faster than 47.09% of Java online submissions for Best Time to Buy and Sell Stock III.
 * Memory Usage: 42.5 MB, less than 7.32% of Java online submissions for Best Time to Buy and Sell Stock III.
 *
 * Copy from: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/solutions/8610/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-lab/[309. 买卖股票的最佳时机含冷冻期 - 一个方法团灭 6 道股票问题^]
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-28 20:14
 */
public int maxProfit(int[] prices) {
    int dp10 = 0, dp11 = Integer.MIN_VALUE;
    int dp20 = 0, dp21 = Integer.MIN_VALUE;
    for (int i = 0; i < prices.length; i++) {
        dp20 = Math.max(dp20, dp21 + prices[i]);
        dp21 = Math.max(dp21, dp10 - prices[i]);
        dp10 = Math.max(dp10, dp11 + prices[i]);
        dp11 = Math.max(dp11, -prices[i]);
    }
    return dp20;
}

/**
 * Runtime: 5 ms, faster than 22.10% of Java online submissions for Best Time to Buy and Sell Stock III.
 * Memory Usage: 42.4 MB, less than 7.32% of Java online submissions for Best Time to Buy and Sell Stock III.
 */
public int maxProfitDpTable(int[] prices) {
    if (Objects.isNull(prices) || prices.length == 0) {
        return 0;
    }
    int maxK = 2;
    int[][][] dp = new int[prices.length][maxK + 1][2];
    for (int i = 0; i < prices.length; i++) {
        for (int k = maxK; k >= 1; k--) {
            if (i == 0) {
                dp[i][k][0] = 0;
                dp[i][k][1] = -prices[i];
                continue;
            }
            dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
            dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
        }
    }
    return dp[prices.length - 1][maxK][0];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-04-27 09:02:36
 */
public int maxProfit(int[] prices) {
  // prices x
  // 交易次数 y
  // 买、卖、不动 买0，卖则为1
  // dp[x][y][z]
  // dp[x][y][0] = max{dp[x-1][y][0], dp[x-1][y][1]+price[x]}
  // dp[x][y][1] = max{dp[x-1][y][1], dp[x-1][y-1][0]-price[x]}
  int maxK = 2;
  int[][][] dp = new int[prices.length][maxK + 1][2];
  for (int x = 0; x < prices.length; x++) {
    for (int y = maxK; y >= 1; y--) {
      if (x == 0) {
        dp[x][y][0] = 0;
        dp[x][y][1] = -prices[x];
        continue;
      }
      dp[x][y][0] = Math.max(dp[x - 1][y][0], dp[x - 1][y][1] + prices[x]);
      dp[x][y][1] = Math.max(dp[x - 1][y][1], dp[x - 1][y - 1][0] - prices[x]);
    }
  }
  return dp[prices.length - 1][maxK][0];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 暴力破解（201/214）
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-01-18 10:45:43
 */
public int maxProfit(int[] prices) {
  return dfs(prices, prices.length - 1, 0, 2);
}

private int dfs(int[] prices, int index, int hold, int step) {
  if (step < 0) {
    return Integer.MIN_VALUE / 2;
  }
  if (index < 0) {
    if (hold == 1) {
      return Integer.MIN_VALUE / 2;
    } else {
      return 0;
    }
  }
  if (hold == 1) {
    return Math.max(dfs(prices, index - 1, 1, step),
      dfs(prices, index - 1, 0, step) - prices[index]);
  }
  // 只在卖出时，更新交易次数。所以，在这里将 step - 1
  return Math.max(dfs(prices, index - 1, 0, step),
    dfs(prices, index - 1, 1, step - 1) + prices[index]);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 暴力破解（201/214）-> 备忘录（14.46%）
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-01-18 22:10:31
 */
public int maxProfit(int[] prices) {
  int[][][] memo = new int[2][3][prices.length];
  for (int[][] ms : memo) {
    for (int[] m : ms) {
      Arrays.fill(m, Integer.MIN_VALUE / 2);
    }
  }
  return dfs(prices, prices.length - 1, 0, 2, memo);
}

private int dfs(int[] prices, int index, int hold, int step, int[][][] memo) {
  // 任何情况下，step 都不能为负
  if (step < 0) {
    return Integer.MIN_VALUE / 2;
  }
  if (index < 0) {
    if (hold == 1) {
      // 第 0 天，不可能持有股票
      return Integer.MIN_VALUE / 2;
    } else {
      // 第 0 天，未持有股票，则利润为 0
      return 0;
    }
  }
  System.out.printf("hold=%d, step=%d, %d, index=%d\n", hold, step, step - 1, index);
  if (memo[hold][step][index] != Integer.MIN_VALUE / 2) {
    return memo[hold][step][index];
  }
  if (hold == 1) {
    return memo[hold][step][index] = Math.max(
      dfs(prices, index - 1, 1, step, memo),
      dfs(prices, index - 1, 0, step, memo) - prices[index]);
  }
  // 只在卖出时，更新交易次数。所以，在这里将 step - 1
  return memo[hold][step][index] = Math.max(
    dfs(prices, index - 1, 0, step, memo),
    dfs(prices, index - 1, 1, step - 1, memo) + prices[index]);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
  /**
   * 暴力破解（201/214）-> 备忘录（14.46%）-> 动态规划
   *
   * @author D瓜哥 · https://www.diguage.com
   * @since 2026-01-18 22:29:51
   */
  public int maxProfit(int[] prices) {
    int n = prices.length;
    int k = 2;
    int[][][] dp = new int[n + 1][k + 2][2];
    for (int[][] ds : dp) {
      for (int[] d : ds) {
        Arrays.fill(d, Integer.MIN_VALUE / 2);
      }
    }
    for (int j = 1; j <= k + 1; j++) {
      dp[0][j][0] = 0;
    }
    for (int index = 1; index <= n; index++) {
      for (int step = 1; step <= 3; step++) {
        dp[index][step][0] = Math.max(dp[index - 1][step][0], dp[index - 1][step - 1][1] + prices[index - 1]);
        dp[index][step][1] = Math.max(dp[index - 1][step][1], dp[index - 1][step][0] - prices[index - 1]);
      }
    }
    return dp[n + 1][k + 1][0];
//    int n = prices.length;
//    int hold = 2;
//    int k = 2;
//    int[][][] dp = new int[hold][k + 1][n + 1];
//    for (int[][] ds : dp) {
//      for (int[] d : ds) {
//        Arrays.fill(d, Integer.MIN_VALUE / 2);
//      }
//    }
//    for (int j = 1; j <= k; j++) {
//      dp[0][j][0] = 0;
//    }
//
//    // dp[1][step][index] = max(dp[1][step][index-1], dp[0][step][index-1] - prices[index])
//    // dp[0][step][index] = max(dp[0][step][index-1], dp[1][step-1][index-1] + prices[index])
//    for (int index = 1; index <= n; index++) {
//      for (int step = 1; step <= 2; step++) {
//        dp[1][step][index] = Math.max(dp[1][step][index - 1], dp[0][step][index - 1] - prices[index - 1]);
//        dp[0][step][index] = Math.max(dp[0][step][index - 1], dp[1][step - 1][index - 1] + prices[index - 1]);
//      }
//    }
//    return dp[0][2][n];
  }

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

友情支持

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

思路分析

参考资料