Microsoft Principal AS 拼接 K 次最大子数组和：Kadane 与跨段前后缀

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版要求非空连续子数组，数组本身非空、K≥1；允许负数。
• 返回数学整数最大和，不取模；如平台有取模要求，不能在求最大时直接对候选取模。
• 数组拼接是按原顺序重复 K 次，不是排列或任意选段。

解题路线

1. 先用 Kadane 求单个副本内部的最佳非空子数组 best。K=1 直接返回。
2. 跨副本的最优连续段必由第一副本的某个后缀、零个或多个完整中间副本、最后副本的某个前缀组成。分别求最大非空 suffix 与 prefix，以及整个数组总和 total。
3. 若 K≥2，跨两副本候选为 suffix+prefix；若 total>0，可再纳入 K−2 个完整副本，增加 (K−2)×total。total≤0 时不应加入额外完整副本。
4. 最终比较 best 与跨副本候选；不必真的生成长度 nK 的数组。

手动走一遍

[1,-2,1] 的单副本 best=1、总和 0、最大前缀/后缀均为 1；K=3 时跨边界可取末尾 1+下副本开头 1=2，答案 2。全负数组 [-3,-1] 无论 K 多大答案仍 -1。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections.abc import Sequence


def max_subarray_k_concatenations(values: Sequence[int], k: int) -> int:
    """Maximum nonempty contiguous sum across k copies of values."""
    if not values or k < 1:
        raise ValueError('nonempty array and k >= 1 required')
    current = best = values[0]
    for value in values[1:]:
        current = max(value, current + value)
        best = max(best, current)
    if k == 1:
        return best
    prefix = running = values[0]
    for value in values[1:]:
        running += value
        prefix = max(prefix, running)
    suffix = running = values[-1]
    for value in reversed(values[:-1]):
        running += value
        suffix = max(suffix, running)
    total = sum(values)
    return max(best, prefix + suffix + max(0, k - 2) * max(0, total))


if __name__ == '__main__':
    assert max_subarray_k_concatenations([1, -2, 1], 3) == 2

复杂度

两三次线性扫描 O(n) 时间、O(1) 额外空间，与 K 大小无关；若结果可能超过固定整数宽度，需用 64 位或大整数。

易错点与追问

容易失分的边界

• 实际拼接 K 次导致 O(nK) 内存/时间。
• 允许空子数组把全负数组错误返回 0。
• total<0 时仍强迫加入 K−2 个完整副本，降低答案。
• 提前对候选取模后比较大小，模序不保序。

继续深挖

• 若要求返回最优区间的全局起止下标，如何处理 K 很大？
• 如果数组每次拼接前可以循环旋转，公式为何失效？
• 若 K=0，应由接口如何定义结果？