基于股票报价最大化利润

1. 概述

在本教程中，我们将讨论如何通过最多执行 K 次交易，最大化买卖商品的利润。我们会先介绍一个朴素解法，然后优化它以获得更高效的解决方案。

最后，我们将对两种方法进行对比，并说明在不同场景下应使用哪种方法。

2. 问题定义

假设我们关注某个商品的价格走势。我们知道该商品未来 n 天的价格，其中第 i 天的价格为 P[i]。因此，我们得到了一个长度为 n 的数组 P。

我们最多可以执行 K 次交易，每次交易必须在前一次交易完成后才能开始。一次交易指的是一次买入和一次卖出。

我们的目标是选择最多 K 对索引，使得在每对索引中我们于第一天买入，第二天卖出，并使得总利润最大化。

换句话说，我们希望最大化：

$$ \sum_{i=0}^{K-1}(P_{s_i} - P_{b_i}) $$

其中 $ s_i \ge b_i $，$ s_i $ 表示卖出日，$ b_i $ 表示买入日。

3. 朴素解法

3.1 思路

我们可以通过动态规划（DP）来解决这个问题。定义 profit[i][k] 为在前 i 天内完成 k 次交易所能获得的最大利润。

在第 i 天，我们有两种选择：

不操作：此时利润等于前 i-1 天的利润，即 profit[i][k] = profit[i-1][k]
卖出：我们需要在之前的某一天 j 买入，然后在第 i 天卖出，此时利润为 profit[j-1][k-1] + P[i] - P[j]

我们需要在所有 j < i 中选择最大值。

3.2 实现

int DynamicProgrammingApproach(int[] P, int n, int K) {
    int[][] profit = new int[n+1][K+1];

    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= K; k++) {
            int max_so_far = 0;
            for (int j = 1; j <= i; j++) {
                max_so_far = Math.max(max_so_far, P[i] - P[j] + profit[j-1][k-1]);
            }
            profit[i][k] = Math.max(profit[i-1][k], max_so_far);
        }
    }

    int answer = 0;
    for (int k = 1; k <= K; k++) {
        answer = Math.max(answer, profit[n][k]);
    }

    return answer;
}

初始化：

profit[i][0] = 0：0 次交易无法获利
profit[0][k] = 0：0 天无法交易

时间复杂度： O(n² * K)

4. 更优解法

4.1 思路

在朴素解法中，我们在每次计算 profit[i][k] 时都要遍历所有 j < i 来找出最优买入点。我们可以优化这个过程。

我们观察到，P[i] 是固定的，因此可以将公式改写为：

$$ maxProfit[i][k] = \max_{j \le i}(profit[j-1][k-1] - P[j]) $$

然后：

$$ profit[i][k] = \max(profit[i-1][k], P[i] + maxProfit[i][k]) $$

这样我们就可以在每次迭代中维护一个前缀最大值，而不需要每次都遍历 j。

4.2 实现

int FasterDynamicProgrammingApproach(int[] P, int n, int K) {
    int[][] profit = new int[n+1][K+1];
    int[][] maxProfit = new int[n+1][K+1];

    // 初始化为极小值
    for (int i = 0; i <= n; i++) {
        for (int k = 0; k <= K; k++) {
            maxProfit[i][k] = Integer.MIN_VALUE;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= K; k++) {
            if (i == 1) {
                maxProfit[i][k] = -P[i];
            } else {
                maxProfit[i][k] = Math.max(maxProfit[i-1][k], profit[i-1][k-1] - P[i]);
            }
            profit[i][k] = Math.max(profit[i-1][k], P[i] + maxProfit[i][k]);
        }
    }

    int answer = 0;
    for (int k = 1; k <= K; k++) {
        answer = Math.max(answer, profit[n][k]);
    }

    return answer;
}

初始化：

profit[i][0] = 0：0 次交易无利润
profit[0][k] = 0：0 天无交易
maxProfit[i][0] = -∞：防止在无交易的情况下卖出
maxProfit[0][k] = -∞：防止在无天数情况下买入

时间复杂度： O(n * K)

5. 对比分析

维度	朴素解法	更优解法
时间复杂度	✅ O(n² * K)	✅ O(n * K)
空间复杂度	❌ O(n * K)	❌ O(n * K)（额外 maxProfit）
实现难度	✅ 简单	⚠️ 略复杂（需维护 maxProfit）
适用场景	数据量小、K 小时使用	数据量大、K 大时使用

6. 小结

在本教程中，我们讨论了如何通过最多 K 次交易最大化股票买卖利润的问题：

首先，我们介绍了基于暴力枚举的动态规划解法，虽然思路简单，但时间效率较低
然后，我们通过优化，利用前缀最大值的思想，将时间复杂度降低到 O(n*K)
最后，我们对比了两种方法的优劣，并给出了使用建议

✅ 适用建议：

当 K 较小或 n 较小时，使用朴素方法
当 K 和 n 都较大时，优先使用优化方法

⚠️ 踩坑提醒：

动态规划数组的初始化必须准确，否则可能导致负利润或错误结果
注意数组索引是否从 0 或 1 开始，避免越界
使用 Integer.MIN_VALUE 来防止非法交易（如未买先卖）

Persistence

REST

Security