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

2024-11-23 HGNULB 约 12 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

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

题意分析

把数组 arr 首尾相接重复 k 次得到一个长数组，求这个长数组中连续子数组的最大和，结果对 $10^9+7$ 取模。子数组允许为空，因此答案下界是 0。

三个信息决定了解法形态。第一，「子数组允许为空」意味着答案永远非负，全负数组的答案是 0 而不是最大的那个负数——这一条会渗透进后面每一个中间量的初值。第二，重复出来的长数组是周期性的，k 段完全相同，这保证了可以只分析 arr 本身并用公式外推。第三，取模只在最后一步做。

约束是关键：arr 长度上限 $10^5$，k 上限 $10^5$。展开后长度可达 $10^{10}$，别说 Kadane 扫一遍，连数组都开不出来。所以必须只扫原数组常数次，再靠数学关系推出答案。

还要注意取模带来的陷阱：题目要求对结果取模，但中间过程绝不能取模——一旦取模，数值的大小关系就被破坏，max 比较会选出错误的分支。正确做法是全程用 64 位整数累加，最后一步再取模。$10^5 \times 10^5 \times 10^4$ 的量级约 $10^{14}$，long 装得下而 int 会溢出。

边界：k = 1 时退化成经典的最大子数组和；数组全负时答案为 0；数组全正时答案是全部元素之和乘 k。

解法：Kadane + 前后缀最大和

核心思路

先看暴力：真的把数组拼 k 次再跑 Kadane，$O(nk)$ 达到 $10^{10}$，时间与空间都不可行。瓶颈在于重复的段被重复扫描了，而它们的内部结构完全一样。

关键观察：最优子数组在拼接后的长数组里，只可能是下面三种形态之一。

形态 A：完全落在某一段内部。 由于每段都一样，它的最大值就是 arr 自身的最大子数组和，记为 bestOne。

形态 B：跨越两段，即「前一段的一个后缀 + 后一段的一个前缀」。 它的最大值是 arr 的最大后缀和 bestSuffix 加上最大前缀和 bestPrefix。注意这两个量互相独立——后缀取在前一段、前缀取在后一段，不会争抢同一个元素。

形态 C：跨越三段或更多，即「一个后缀 + 若干个完整段 + 一个前缀」。 中间那些完整段每个贡献 sum（数组总和）。若最优解跨越了 m 段（$m \ge 3$），中间就有 m - 2 个完整段。

形态 C 只在 sum > 0 时才值得考虑：整段的贡献是 sum，若 sum <= 0，多包一段只会让和不增，直接退化回形态 B。而当 sum > 0 时，包的完整段越多越好，所以 m 应取到最大值 k，中间段数为 k - 2。

三种形态合并成一个式子：
\[ans = \max\Big(bestOne,\ \underbrace{bestPrefix + bestSuffix + \max(k-2,\ 0)\cdot \max(sum,\ 0)}_{k \ge 2\ \text{时才参与}}\Big)\]
这就是全部推导。剩下的是四个量怎么算，以及初值为什么都取 0。

bestOne 用 Kadane：维护 cur = max(0, cur + v)，含义是「以当前位置结尾的最大子数组和，允许为空所以下界 0」，bestOne 取过程最大值。cur 一旦为负就归零，等价于「丢掉前面的累赘，从这里重新开始」。

bestPrefix：前缀和的过程最大值，初值 0 表示可以取空前缀。

bestSuffix：从右往左累加的过程最大值，初值 0 同理。

sum：全部元素之和，它可正可负，参与计算时才用 sum > 0 判断。

所有 best* 的初值都取 0，这一条统一地把「子数组可以为空」这个规则编码进了每个中间量，于是全负数组自然得到 0，不需要任何特判。这是本题最容易被忽略却最省事的设计。

不变量：bestOne、bestPrefix、bestSuffix 三者在各自的循环中始终等于「已扫描部分对应含义的最大值，且不小于 0」。

正确性：任意连续子数组要么位于一个副本内，要么跨两个副本，要么跨至少三个副本，三种形态没有遗漏。前两类最优值分别是 bestOne 与 bestSuffix + bestPrefix；第三类必然包含首尾之间的完整副本，sum > 0 时取满 k - 2 个最优，sum <= 0 时一个也不取更优。代码分别求出各类最优值并取最大，因此在 k = 1、k = 2 和 k > 2 时都返回全局最优解。

解题步骤

第一趟 Kadane 求 bestOne：cur = Math.max(0, cur + v)，随后 bestOne = Math.max(bestOne, cur)。把「归零」写进 cur 的更新里，比写成 if (cur < 0) cur = 0 更紧凑；两者等价。bestOne 初值 0 承担了「空子数组」的语义。

第二趟求 bestPrefix 与 sum：一边累加 prefix 一边取最大值，同时把 sum 累出来。两者可以合在同一个循环里，因为都是从左往右的前缀累加。

第三趟从右往左求 bestSuffix：必须反向遍历。后缀和不能由「总和减前缀和」直接取最大——那样得到的是 sum - min(prefix)，虽然数学上等价，但在 bestSuffix 需要与 0 取大的语义下还要额外处理，反向扫一趟更直白也更不易错。

拼装答案：answer = bestOne；若 k > 1，令 cross = bestPrefix + bestSuffix，再在 sum > 0 时加上 (k - 2) * sum，最后与 answer 取大。k > 1 的判断是必须的——k == 1 时根本没有第二段，bestPrefix + bestSuffix 会把同一段的前缀与后缀相加，可能重复计算元素得到虚高的值。而 k == 2 时 k - 2 = 0，乘出来是 0，cross 自然退化成形态 B，无需再分一个case。

中间量统一用 long：代码中的 sum 已是 long，所以 Java 会先把 (k - 2) 提升为 long 再相乘；显式写成 (long) (k - 2) * sum 是为了让这个溢出边界一眼可见。若两侧都用 int，则必须在乘法前提升类型。

最后一步取模：(int) (answer % MOD)。中间任何一步取模都会破坏大小比较。

以 arr = [1, -2, 1]、k = 5 走一遍（答案 2）：

Kadane：cur = max(0, 0+1) = 1，bestOne = 1；cur = max(0, 1-2) = 0，bestOne = 1；cur = max(0, 0+1) = 1，bestOne = 1。得 bestOne = 1。

前缀：prefix 依次为 1、-1、0，bestPrefix = 1；sum = 0。

后缀：从右往左 suffix 依次为 1、-1、0，bestSuffix = 1。

拼装：k = 5 > 1，cross = 1 + 1 = 2；sum = 0 不大于 0，不加中间段；answer = max(1, 2) = 2。

验证一下：展开后是 [1,-2,1, 1,-2,1, 1,-2,1, 1,-2,1, 1,-2,1]，最大子数组是跨段的 [1, 1]（第一段末尾的 1 加第二段开头的 1），和为 2。而 sum = 0 说明多包完整段毫无收益，所以答案不随 k 增大而增大——这正是 sum > 0 判断的意义。

再以 arr = [1, 2]、k = 3 走一遍（答案 9）：bestOne = 3；bestPrefix = 3（整段）；bestSuffix = 3；sum = 3 > 0。cross = 3 + 3 + (3-2) * 3 = 9，answer = max(3, 9) = 9。展开后是 [1,2,1,2,1,2]，全取即 9，正确。

再以 arr = [-1, -2]、k = 7 走一遍（答案 0）：Kadane 中 cur 始终被压回 0，bestOne = 0；bestPrefix = 0、bestSuffix = 0；sum = -3。cross = 0 + 0 = 0（sum 不大于 0 不加中间段），answer = 0。空子数组胜出，全靠三个初值取 0 自然得到，没有一行特判。

最后看 k = 1 为什么必须挡住：设 arr = [3, -10, 3]、k = 1。bestOne = 3（正确答案）。但 bestPrefix = 3、bestSuffix = 3，若不判 k > 1 就算 cross = 6，相当于把第一个 3 和第三个 3 拼在一起——它们中间隔着 -10，在只有一段的数组里根本不相邻，答案会错成 6。

代码实现

class Solution {
    private static final int MOD = 1_000_000_007;

    public int kConcatenationMaxSum(int[] arr, int k) {
        // 形态 A：完全落在一段内。初值 0 表示允许空子数组。
        long bestOne = 0;
        long cur = 0;
        for (int v : arr) {
            cur = Math.max(0, cur + v);
            bestOne = Math.max(bestOne, cur);
        }

        long sum = 0;
        long bestPrefix = 0;
        long prefix = 0;
        for (int v : arr) {
            prefix += v;
            bestPrefix = Math.max(bestPrefix, prefix);
            sum += v;
        }

        long bestSuffix = 0;
        long suffix = 0;
        for (int i = arr.length - 1; i >= 0; i--) {
            suffix += arr[i];
            bestSuffix = Math.max(bestSuffix, suffix);
        }

        long answer = bestOne;
        if (k > 1) {
            // 形态 B：后缀 + 前缀；sum > 0 时再补上 k-2 个完整段（形态 C）。
            long cross = bestPrefix + bestSuffix;
            if (sum > 0) {
                cross += (long) (k - 2) * sum;
            }
            answer = Math.max(answer, cross);
        }

        // 只在最后取模，中间取模会破坏 max 的比较。
        return (int) (answer % MOD);
    }
}

func kConcatenationMaxSum(arr []int, k int) int {
	const mod = 1000000007

	// 形态 A：完全落在一段内。初值 0 表示允许空子数组。
	bestOne := int64(0)
	cur := int64(0)
	for _, v := range arr {
		cur = max64(0, cur+int64(v))
		bestOne = max64(bestOne, cur)
	}

	sum := int64(0)
	bestPrefix := int64(0)
	prefix := int64(0)
	for _, v := range arr {
		prefix += int64(v)
		if prefix > bestPrefix {
			bestPrefix = prefix
		}
		sum += int64(v)
	}

	bestSuffix := int64(0)
	suffix := int64(0)
	for i := len(arr) - 1; i >= 0; i-- {
		suffix += int64(arr[i])
		if suffix > bestSuffix {
			bestSuffix = suffix
		}
	}

	answer := bestOne
	if k > 1 {
		// 形态 B：后缀 + 前缀；sum > 0 时再补上 k-2 个完整段（形态 C）。
		cross := bestPrefix + bestSuffix
		if sum > 0 {
			cross += int64(k-2) * sum
		}
		if cross > answer {
			answer = cross
		}
	}

	// 只在最后取模，中间取模会破坏比较。
	return int(answer % mod)
}

func max64(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 为原数组长度。三趟线性扫描（Kadane、前缀、后缀）加常数次算术，与 k 完全无关——这正是把 $O(nk)$ 的展开模拟压成公式外推的收益。

空间复杂度：$O(1)$，只用了 bestOne、cur、prefix、bestPrefix、sum、suffix、bestSuffix 七个 64 位标量，没有分配任何与输入规模相关的结构。

关键点总结

面对「周期性重复的超长序列」，先把最优解按跨越了多少个周期分类：段内、跨两段、跨多段。分类穷尽后每一类都能用原数组的常数个统计量表达，k 就只以系数形式出现。

中间完整段只在 sum > 0 时才值得包含——判断「多加一个周期是否有收益」是这类题的通用开关。

「子数组可以为空」应当通过把所有 best* 的初值设为 0 来统一实现，而不是在末尾补一句 max(ans, 0)，更不是为全负数组写特判。

取模只能在最后一步做：中间取模会改变数值的相对大小，让 max 选错分支。这是取模类题目的头号陷阱。

大数相乘要先把操作数提升到 64 位再乘，(long) (k - 2) * sum 中的强转位置不能挪到乘法之后。

k == 1 必须单独挡住，否则会把同一段的前缀与后缀相加，凭空拼出不相邻的元素。

面试视角：本题是 53 题的进阶包装，答题时应先说「展开不可行，$10^{10}$」，再给出三种形态的分类，最后才写代码。面试官常追问「为什么 k - 2 而不是 k - 1」和「sum <= 0 时会怎样」，这两问的答案就在形态 C 的推导里。

易错点总结

错误写法：先把候选和分别取模，再比较大小。用例 arr 由 $10^5$ 个 $10^4$ 组成、k = 10^5：真实跨段和约为 $10^{14}$，取模后可能小于单段和；此时 max 会选错候选。必须先比较真实值，最终答案只取模一次。

错误写法：用 int 累加。用例 arr 全为 $10^4$、长度 $10^5$、k = 10^5：(k-2) * sum 达到 $10^{14}$ 量级，int 溢出成负数，答案变成 bestOne 甚至负值。

错误写法：把总和存在 int sumInt 中，再写 (long) ((k - 2) * sumInt)。用例同上：两个 int 先按 32 位溢出，再转 long 也救不回来；应写 (long) (k - 2) * sumInt，或从一开始就让 sum 为 long。

错误写法：不判 k > 1 就计算 bestPrefix + bestSuffix。用例 arr = [3, -10, 3]、k = 1：得到 6，而只有一段时这两个 3 并不相邻，正确答案是 3。

错误写法：无论 sum 正负都加上 (k - 2) * sum。用例 arr = [5,-10,4]、k = 3：sum = -1，正确跨段答案是后缀 4 加前缀 5，等于 9；错误地再塞入一个完整段后只剩 8，即使最后与单段最优值 5 取大也救不回来。

错误写法：Kadane 写成 cur = Math.max(v, cur + v)（不允许空子数组）且 bestOne 初值取 arr[0]。用例 arr = [-1, -2]、k = 7：返回 -1，而题目允许空子数组，正确答案是 0。

错误写法：bestPrefix 或 bestSuffix 初值取 Long.MIN_VALUE 或首元素。用例 arr = [-1, -2]：bestPrefix 变成 -1，cross 变成 -2，虽然被 max(bestOne, ...) 兜住，但一旦某处直接返回 cross 就会得到负数。

错误写法：真的把数组拼 k 次再跑 Kadane。用例 n = 10^5、k = 10^5：需要 $10^{10}$ 个元素，内存直接爆掉。

错误写法：用 sum - minPrefix 求 bestSuffix 却忘了与 0 取大。用例 arr = [-1, -2]：算出的后缀最大值为 -1 而非 0，与「允许空后缀」的语义不符。

错误写法：k - 2 写成 k - 1。用例 arr = [1, 2]、k = 3：cross = 3 + 3 + 2*3 = 12，超过了长数组的元素总和 9，答案偏大。

错误写法：把 bestOne 与 cross 分别取模后再比较。用例大数据：取模后两者的相对大小与真实值无关，max 的结果随机。

相似题目

题目	难度	考察点
53. 最大子数组和	中等	本题形态 A 的原型，Kadane 的标准模板
918. 环形子数组的最大和	中等	只绕一圈的特例，用「总和减最小子数组和」处理跨界，与本题分类思路互补
1186. 删除一次得到子数组最大和	中等	在 Kadane 上加一维状态记录「是否已删除」，考察状态扩展
152. 乘积最大子数组	中等	把加法换成乘法后需同时维护最大与最小值，展示 Kadane 的适用边界
剑指 Offer 42. 连续子数组的最大和	简单	与 53 同题，可用于固化模板
面试题 16.17. 连续数列	简单	同为 Kadane 的基础练习，注意它不允许空子数组，与本题初值取 0 形成对照