1191. K 次串联后最大子数组之和

发表于 2026-01-02 分类于力扣阅读次数： Waline：本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

最大子数组和

思路

一、问题描述（抽象建模）

给定一个长度为 $n$ 的整数数组 \[ \texttt{arr} = [a_0, a_1, \dots, a_{n-1}] \] 将其按顺序拼接 $k$ 次，得到新数组： \[ \texttt{arr}^{(k)} = \underbrace{\texttt{arr} \Vert \texttt{arr} \Vert \cdots \Vert \texttt{arr}}_{k\ \text{次}} \] 要求在 $\texttt{arr}^{(k)}$ 中，求最大子数组和。允许选择空子数组，因此答案不小于 $0$。

二、核心观察（问题降维）

直接在长度为 $kn$ 的数组上求最大子数组和是不可行的。关键在于：最优子数组的结构是高度受限的。

任意一个跨越数组拼接边界的子数组，其形式必然是：

某一份数组的后缀
加上若干个完整数组
再加上一份数组的前缀

因此，整个问题可以被压缩为对原数组的若干“统计量”的组合。

三、必须计算的四个量（问题的本质）

对原数组 arr，一次线性扫描即可得到以下四个量：

1. 数组总和

\[ S = \sum_{i=0}^{n-1} a_i \]

2. 单数组最大子数组和

记为： \[ M_1 = \max_{\text{subarray} \subseteq \texttt{arr}} \sum \text{subarray} \] 使用 Kadane 算法，并在最后与 $0$ 取最大值（允许空子数组）。

3. 最大前缀和

\[ P = \max_{0 \le i < n} \sum_{j=0}^{i} a_j \]

4. 最大后缀和

\[ Q = \max_{0 \le i < n} \sum_{j=i}^{n-1} a_j \]

四、关键分类讨论（设计思路）

情况一：$k = 1$

不涉及拼接，答案显然为： \[ \max(0, M_1) \]

情况二：$k \ge 2$

最大子数组只有两种可能来源：

情形 A：完全位于某一个数组内部

最大值为： \[ M_1 \]

情形 B：跨越数组拼接边界

此时子数组结构为： \[ \text{后缀} + \text{若干完整数组} + \text{前缀} \] 其最大值为： \[ Q + (k-2)\cdot S + P \] 但注意：是否值得取中间的完整数组，取决于 $S$ 的符号。

五、跨边界方案的通式

当 $k \ge 2$ 时，最大子数组要么：

完全落在某一个块内，取到 $M_1$；
跨越边界。

下面集中讨论跨边界情况。

设某个候选子数组覆盖了从第 $L$ 块到第 $R$ 块（$0 \le L \le R \le k-1$）。若 $L=R$，那就回到单块内部，最大不超过 $M_1$。若 $L，该子数组的和可以写成： \[ \text{Sum} = \underbrace{\text{Suffix}(\texttt{arr})}_{\le Q} + \underbrace{(R-L-1)\cdot S}_{\text{中间整块}} + \underbrace{\text{Prefix}(\texttt{arr})}_{\le P} \] 因此跨边界子数组的最大可能值为： \[ Q + t\cdot S + P \] 其中 \[ t = R-L-1 \] 表示中间被完整覆盖的整块数量，并且满足： \[ 0 \le t \le k-2 \] 问题转化为：在固定 $P,Q,S$ 的前提下，如何选择 $t$ 才能使 \[ Q + t\cdot S + P \] 最大。

六、关键数学解释：为什么仅当 $S>0$ 才“把中间整块全部纳入”

对于跨边界形式 \[ F(t)=Q + P + t\cdot S,\quad t \in [0, k-2] \] 最优的 $t$ 取值满足：

若 $S>0$，则 $t=k-2$（纳入尽可能多的整块）；
若 $S\le 0$，则 $t=0$（不纳入任何中间整块）。

中间每多纳入一个完整数组，子数组和会额外增加 $S$。

$S>0$：每加入一份完整数组都赚正收益，越多越好；
$S\le 0$：每加入一份完整数组不赚甚至亏，最优不会多加入。

七、最终结论（统一公式）

若 $S \le 0$

中间完整数组只会降低总和，因此最多跨越一次边界： \[ \text{Ans} = \max\left(M_1,\; P + Q\right) \]

若 $S > 0$

中间完整数组全部纳入是有利的： \[ \text{Ans} = \max\left(M_1,\; P + Q + (k-2)\cdot S\right) \]

八、时间与空间复杂度

时间复杂度： \[ O(n) \]
空间复杂度： \[ O(1) \]

九、AC代码

class Solution {
public:
    static const int mod = 1e9 + 7;
    using ll = long long;

    int kConcatenationMaxSum(vector<int>& arr, int k) {
        int n = arr.size();

        // 1. 数组总和 S
        ll sum = arr[0];

        // 2. 最大前缀和 P
        ll maxPrefix = arr[0];

        // 3. 单数组最大子数组和 M1（Kadane）
        ll cur = arr[0];
        ll maxSub = arr[0];

        for (int i = 1; i < n; ++i) {
            sum += arr[i];

            // 前缀和更新
            maxPrefix = max(maxPrefix, sum);

            // Kadane
            cur = max((ll)arr[i], cur + arr[i]);
            maxSub = max(maxSub, cur);
        }

        // 4. 最大后缀和 Q
        ll maxSuffix = arr[n - 1];
        ll suffixSum = arr[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            suffixSum += arr[i];
            maxSuffix = max(maxSuffix, suffixSum);
        }

        // 允许空子数组
        maxSub = max(0LL, maxSub);

        // k == 1 的特殊情况
        if (k == 1) {
            return (int)(maxSub % mod);
        }

        // k >= 2
        ll ans;
        if (sum <= 0) {
            // 最多跨一次边界
            ans = max(maxSub, maxPrefix + maxSuffix);
        } else {
            // 中间完整数组全部纳入
            ans = max(maxSub, maxPrefix + maxSuffix + (ll)(k - 2) * sum);
        }

        return (int)(ans % mod);
    }
};