购买股票的最佳时机III和IV

购买股票的最佳时机III

题目描述：

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润（你最多可以完成两笔交易）。

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

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：

在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3

解题思路

问题定义：
- 我们需要在给定的股票价格数组中计算在最多 k 次交易下能获得的最大利润。
- 交易的定义是一次买入和一次卖出。
特殊情况处理：
- 如果价格数组为空或交易次数为零，最大利润为零。
简化情况：
- 如果允许的交易次数 k 大于等于 n/2（即可以进行无限次交易），则可以通过计算所有价格的上升段来获取最大利润。
动态规划：
- 创建一个二维数组 profit，其中 profit[i][j] 表示在前 j 天内进行最多 i 次交易的最大利润。
- 初始化 profit 数组的第一列为零，因为在没有交易的情况下利润为零。
填充利润矩阵：
- 对于每个交易次数 i（从1到k），遍历每一天 j（从1到n），计算：
  - 当前利润为 profit[i][j-1]（不进行交易）和 prices[j] + maxDiff（进行交易）中的较大值。
  - maxDiff 记录的是前一天的利润减去当前价格的最大值，以便在后续计算中使用。
打印利润矩阵：
- 在填充完成后，打印出利润矩阵，以便观察每一步的计算结果。
最终结果：
- 输出 profit[k][n-1]，即在前 n 天内进行最多 k 次交易的最大利润。

状态转移方程

状态定义
- profit[i][j] 表示在前 j 天内，最多进行 i 次交易所获得的最大利润。

基本情况：
- 如果没有交易次数（i = 0），则无论天数 j，最大利润都是 0：
  profit[0][j]=0∀j
- 如果没有天数（j = 0），则无论交易次数 i，最大利润也是 0：
  profit[i][0]=0∀i
状态转移：
对于每个交易次数 i 和每一天 j，我们有两种选择：
- 不进行交易：在第 j 天的最大利润与前一天相同：
  profit[i][j]=profit[i][j−1]
- 进行交易：在第 j 天卖出股票，之前的利润加上当前价格与之前最大差值的和：
  profit[i][j]=prices[j]+maxDiff 其中，maxDiff 是在前 j 天内，考虑到之前的交易所能获得的最大利润减去当前价格。
更新 maxDiff：
在每一天 j，我们需要更新 maxDiff：
maxDiff=max(maxDiff,profit[i−1][j]−prices[j])
这表示在进行第 i 次交易时，考虑到之前的利润减去当前价格，找到最大差值。

总结
最终，最大利润可以通过访问利润矩阵的最后一个元素得到：
最大利润=profit[k][n−1]
这表明在前 n 天内，最多进行 k 次交易所获得的最大利润。
输出
代码中还打印了利润矩阵 profit，便于观察不同交易次数和天数下的利润变化。

Java代码实现

以下是实现上述思路的 Java 代码：

public class MaxProfit {public static void main(String[] args) {int[] prices = {1, 2, 3, 4, 5}; // 股票价格int k = 2; // 最大交易次数int n = prices.length;// 特殊情况处理if (n == 0 || k == 0) {System.out.println("最大利润为: 0");return;}// 如果交易次数大于等于 n/2，直接计算最大利润if (k >= n / 2) {int maxProfit = 0;for (int i = 1; i < n; i++) {if (prices[i] > prices[i - 1]) {maxProfit += prices[i] - prices[i - 1];}}System.out.println("最大利润为: " + maxProfit);return;}// 创建利润矩阵int[][] profit = new int[k + 1][n];// 填充利润矩阵for (int i = 1; i <= k; i++) { // 交易次数int maxDiff = -prices[0]; // 初始化最大差值for (int j = 1; j < n; j++) { // 天数// 更新当前利润profit[i][j] = Math.max(profit[i][j - 1], prices[j] + maxDiff);// 更新最大差值maxDiff = Math.max(maxDiff, profit[i - 1][j] - prices[j]);}}// 打印利润矩阵System.out.println("利润矩阵：");for (int i = 0; i <= k; i++) {for (int j = 0; j < n; j++) {System.out.print(profit[i][j] + "\t");}System.out.println();}// 最终结果System.out.println("最大利润为: " + profit[k][n - 1]);}
}

示例

示例 1

输入: prices = [3, 3, 5, 0, 0, 3, 1, 4]
动态规划矩阵:

       0   1   2   3   4   5   6   7---------------------------------
k=0 |  0   0   0   0   0   0   0   0
k=1 |  0   0   2   2   3   3   3   3
k=2 |  0   0   2   2   3   3   6   6

输出: 6

示例 2

输入: prices = [1, 2, 3, 4, 5]
动态规划矩阵:

       0   1   2   3   4   -----------------------
k=0 |  0   0   0   0   0   
k=1 |  0   1   2   3   4
k=2 |  0   1   2   3   4

输出: 4

示例 3

输入: prices = [7, 6, 4, 3, 1]
动态规划矩阵:

       0   1   2   3   4-----------------------
k=0 |  0   0   0   0   0
k=1 |  0   0   0   0   0
k=2 |  0   0   0   0   0

输出: 0

示例 4

输入: prices = [1, 4, 2, 5, 3, 6]
动态规划矩阵:

       0   1   2   3   4   5-------------------------
k=0 |  0   0   0   0   0   0
k=1 |  0   0   3   3   4   5
k=2 |  0   0   3   4   4   7

输出: 7

示例 5

输入: prices = [3, 2, 6, 5, 0, 3]
动态规划矩阵:

       0   1   2   3   4   5-------------------------
k=0 |  0   0   0   0   0   0
k=1 |  0   0   4   4   4   4
k=2 |  0   0   4   6   6   7

输出: 7

每个动态规划矩阵的行表示交易次数（k），列表示天数（d），矩阵中的值表示在该天结束时的最大利润。通过这些矩阵，我们可以清楚地看到在不同的价格数组中，如何通过最多两笔交易获得最大利润。

利润矩阵填充过程

利润矩阵的结构

我们定义一个二维数组 profit，其大小为 (k+1) x n，其中：

k 是允许的最大交易次数。
n 是价格数组的长度。
profit[i][j] 表示在前 j 天内进行最多 i 次交易的最大利润。

矩阵初始化

第一行和第一列：
- profit[0][j]（第0行）始终为0，因为没有交易时利润为0。
- profit[i][0]（第0列）也为0，因为在没有天数的情况下无法进行交易。

填充利润矩阵的步骤

我们将通过动态规划的方法填充利润矩阵。具体步骤如下：

外层循环（交易次数）：
- 从 i = 1 到 k，表示当前允许的交易次数。
内层循环（天数）：
- 从 j = 1 到 n-1，表示当前的天数。
计算当前利润：
- 对于每个 profit[i][j]，我们需要考虑两种情况：
  1. 不进行交易：即保持前一天的利润 profit[i][j-1]。
  2. 进行交易：即在第 j 天卖出，之前的最佳状态是 prices[j] + maxDiff，其中 maxDiff 是在前 j-1 天内的最大利润减去当前价格 prices[j]。
更新 maxDiff：
- maxDiff 是一个辅助变量，用于记录前一天的利润减去当前价格的最大值。
- 在每次内层循环中更新 maxDiff 的值，以便后续计算使用。

详细示例

假设价格数组为 {1, 2, 3, 4, 5}，最大交易次数 k = 2。

初始化：

profit = [[0, 0, 0, 0, 0],  // 0次交易[0, 0, 0, 0, 0],  // 1次交易[0, 0, 0, 0, 0]   // 2次交易
]

填充过程：

i = 1（1次交易）：
- j = 1：maxDiff = -1 (initially)
  - profit[1][1] = max(0, 2 - 1) = 1
  - 更新 maxDiff = max(-1, 0 - 2) = -1
- j = 2：
  - profit[1][2] = max(1, 3 - 1) = 2
  - 更新 maxDiff = max(-1, 1 - 3) = -1
- j = 3：
  - profit[1][3] = max(2, 4 - 1) = 3
  - 更新 maxDiff = max(-1, 2 - 4) = -1
- j = 4：
  - profit[1][4] = max(3, 5 - 1) = 4
  - 更新 maxDiff = max(-1, 3 - 5) = -1

最终，profit 矩阵更新为：

profit = [[0, 0, 0, 0, 0],[0, 1, 2, 3, 4],[0, 0, 0, 0, 0]
]

i = 2（2次交易）：
- j = 1：maxDiff = -1
  - profit[2][1] = max(0, 2 - 1) = 1
  - 更新 maxDiff = max(-1, 0 - 2) = -1
- j = 2：
  - profit[2][2] = max(1, 3 - 1) = 2
  - 更新 maxDiff = max(-1, 1 - 3) = -1
- j = 3：
  - profit[2][3] = max(2, 4 - 1) = 3
  - 更新 maxDiff = max(-1, 2 - 4) = -1
- j = 4：
  - profit[2][4] = max(3, 5 - 1) = 4
  - 更新 maxDiff = max(-1, 3 - 5) = -1

最终，profit 矩阵更新为：

profit = [[0, 0, 0, 0, 0],[0, 1, 2, 3, 4],[0, 1, 2, 3, 4]
]

总结
- 通过上述步骤，我们填充了利润矩阵，最终得到了在最多进行 k 次交易的情况下，前 n 天的最大利润。
- 最终的结果 profit[k][n-1] 即为所求的最大利润。对于这个例子，最大利润为 4。

购买股票的最佳时机III和IV