买卖股票的最佳时机 III
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^50 <= prices[i] <= 10^5
限制交易次数最大为2。
动态规划-数组递推-正序遍历次数
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0; // 如果没有价格信息，利润为0
}
int n = prices.length;
k = Math.min(k, n / 2); // 最大交易次数不能超过 n/2
// 定义二维数组 buy 和 sell
// own[i][j] 表示第 i 天最多进行 j 次交易且持有股票的最大利润
// not[i][j] 表示第 i 天最多进行 j 次交易且不持有股票的最大利润。注意0次交易这种情况。
int[][] own = new int[n][k + 1];
int[][] not = new int[n][k + 1];
// 初始化第0天的 base case
// 注意一次交易指的是买入和卖出。
own[0][0] = -prices[0];
not[0][0] = 0;
for (int j = 1; j <= k; ++i) {
own[0][j] = not[0][j] = Integer.MIN_VALUE / 2; // 设置为较小的值，避免影响后续计算。重点。
}
// 遍历天数，从第1天开始
for (int i = 1; i < n; ++i) {
// 第i天，不进行任何交易时的持有和不持有股票的最大利润
// 倒序遍历可以省略buy[i][0]的计算。
// not[i][0]=not[i-1][0]=...=not[0][0]=0
// 注意只买入不消耗交易次数
own[i][0] = Math.max(own[i - 1][0], not[i - 1][0] - prices[i]);
for (int j = 1; j <= 2; ++j) {
// 第i天，进行j次交易且持有股票的最大利润。注意，卖出才算一次交易，只买不卖不算。
own[i][j] = Math.max(own[i - 1][j], not[i - 1][j] - prices[i]);
// 第i天，进行j次交易且不持有股票的最大利润
not[i][j] = Math.max(not[i - 1][j], own[i - 1][j - 1] + prices[i]);
}
}
// 返回第n-1天，最多进行k次交易且不持有股票的最大利润。
// 注意不要求一定是k次，是最多k次交易。
return Arrays.stream(not[n - 1]).max().getAsInt();
}
}- 时间复杂度：O(nk)，其中 n 为数组的长度，k 为最大交易次数。
- 空间复杂度：O(nk)。我们需要开辟 O(nk) 空间存储动态规划中的所有状态。
贪心，滚动更新
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0; // 如果没有价格信息，利润为0
}
int n = prices.length;
k = Math.min(k, n / 2); // 最大交易次数不能超过 n/2
// 定义一维数组 buy 和 sell
// buy[j] 表示第 i 天最多进行 j 次交易且持有股票的最大利润
// sell[j] 表示第 i 天最多进行 j 次交易且不持有股票的最大利润
int[] buy = new int[k + 1];
int[] sell = new int[k + 1];
// 初始化第0天的 base case
buy[0] = -prices[0];
sell[0] = 0;
for (int i = 1; i <= k; ++i) {
buy[i] = sell[i] = Integer.MIN_VALUE / 2; // 设置为较小的值，避免影响后续计算
}
// 遍历价格数组，从第1天开始
for (int i = 1; i < n; ++i) {
// 第i天，不进行任何交易时的持有和不持有股票的最大利润。sell[0]不改变，还是0。
buy[0] = Math.max(buy[0], sell[0] - prices[i]);
for (int j = 1; j <= 2; ++j) {
// 第i天，进行j次交易且持有股票的最大利润
buy[j] = Math.max(buy[j], sell[j] - prices[i]);
// 第i天，进行j次交易且不持有股票的最大利润
sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);
}
}
// 返回最多进行k次交易且不持有股票的最大利润
return Arrays.stream(sell).max().getAsInt();
}
}动态规划-数组递推，倒序遍历次数
class Solution {
public int maxProfit(int[] prices) {
int max_k = 2; // 最多进行2次交易
int n = prices.length; // 获取价格数组的长度
// 定义三维数组 dp，其中 dp[i][k][0] 表示第 i 天最多进行 k 次交易且不持有股票的最大利润，
// dp[i][k][1] 表示第 i 天最多进行 k 次交易且持有股票的最大利润
int[][][] dp = new int[n][max_k + 1][2];
// 遍历每一天
for (int i = 0; i < n; i++) {
// 可正序可倒序遍历交易次数，因为dp[i][k][1]依赖于dp[i-1][k-1][0]，这是上一轮的k-1，不是本轮的。
// 如果要正序遍历，则需要单独计算dp[i][0][0]=Math.max(dp[i - 1][0][0], dp[i - 1][0][1] - prices[i]);
// dp[i][0][1]保持0即可，因为已进行0次交易次数时手里不可能有股票。
// i=0时由下面的if处理，正序遍历就不需要下面的if了，反而需要上面的操作
for (int k = max_k; k >= 1; k--) {
// 处理 base case
if (i - 1 == -1) {
// 第0天，不持有股票的最大利润为0，持有股票的最大利润为负的价格
dp[i][k][0] = 0;
dp[i][k][1] = -prices[i];
continue;
}
// 第 i 天不持有股票的最大利润
dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
// 第 i 天持有股票的最大利润
dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
}
// 返回第 n-1 天最多进行 max_k 次交易且不持有股票的最大利润
return dp[n - 1][max_k][0];
}
}