企业官网建设流程全解析

动态规划入门绕不开“最大子数组和”，这道题本身有很经典的 Kadane 算法，网上教程一搜一大把。但一旦题目加了个前缀变成“把数组重复 K 次再求最大子数组和”，很多人就懵了，编号 1191 的这道题就是典型代表。我第一次见到它时，第一反应是“直接把数组拼起来不就行了”，结果发现 K 的上限能到 10^9，真把数组造出来内存直接炸穿。这篇文章我从经典的最大子数组和开始讲，把 Kadane 算法的本质拆开，再一步步推导 K 次串联后的三种情况，最后给出可直接提交的完整代码和实践中容易踩的坑。适合已经能独立写出 Kadane、想挑战变形题的读者，也适合刚接触 DP、想通过一道题打通一类题的人。

1. 先搞定地基：最大子数组和是怎么用 DP 解决的

1.1 问题定义与暴力解法

最大子数组和（也叫最大子段和）的问题描述很简单：给定一个整数数组，找一个连续的子数组，让它的和最大。比如数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]，最大子数组是[4, -1, 2, 1]，和是 6。

如果没学过动态规划，最直觉的做法是枚举所有可能的左右端点，也就是三重循环：外层枚举左端点，中层枚举右端点，内层累加求和。这样时间复杂度是 O(n^3)。稍微优化一下，把内层累加改成边枚举边累加，能降到 O(n^2)，但本质上还是枚举所有连续区间。

在 n 只有几十几百的时候，这些方法都能跑。可一旦 n 到 10^5 甚至 10^6，O(n^2) 基本就是等死。这也是为什么我们需要找规律，而不是纯靠暴力枚举。

1.2 一维 DP 状态的设计思路

动态规划解决这个问题的核心，在于找到一个好的状态定义。这里有个非常经典的思路：我们不去想“任意一段的最大和”，而是限制一下终点。

定义dp[i]表示：以第i个元素结尾的所有子数组中，能得到的最大和。

有了这个状态，转移就变得很自然。对于第i个元素，它只有两种选择：

• 跟前面连起来，组成一个更长的子数组，此时和是dp[i-1] + a[i]
• 自己单干，从a[i]重新开始一段子数组，此时和就是a[i]

到底选哪个，取决于dp[i-1]是否大于 0。如果dp[i-1]是正的，那加上它肯定能让a[i]变得更大；如果dp[i-1]是负的，那加上它只会拖累a[i]，不如直接从当前元素重新开始。

所以转移方程是：

dp[i] = max(a[i], dp[i-1] + a[i])

最终答案就是所有dp[i]里的最大值。

你可能已经发现，这个状态不是“全局最大”，而是“以某个元素结尾的最大”。这种思路在区间型 DP 里非常常用，因为只要把终点定下来，转移就只有一个方向，不会出现左右乱跳的情况。

1.3 滚动变量与 Kadane 算法

上面用dp数组的方式已经很好了，但仔细观察会发现，dp[i]只依赖dp[i-1]，前面那些状态用完就再也不会用到。所以我们完全可以只用一个变量cur来保存“以当前元素结尾的最大子数组和”，再用另一个变量best保存历史最大值。

这就是 Kadane 算法的核心，代码极短：

cur = best = 0 for x in arr: cur = max(x, cur + x) best = max(best, cur)

这里有一个细节要注意：如果题目允许“空子数组”存在，那么空子数组的和是 0，所以初始化cur和best为 0 是合理的。如果题目不允许空子数组，也就是每个子数组至少要有一个元素，那么初始化时需要把best设成一个极小值，或者直接初始化为arr[0]，然后从第二个元素开始遍历。

Kadane 算法为什么看起来像贪心？因为它本质上是在说：一旦累加和变成负数，就果断放弃这一段，从下一个位置重新开始。这个“放弃”的操作非常重要，它保证了状态不会因为前面一段负收益而让整体变差。理解了这一步，后面 1191 题的推导就顺了。

2. 题目一变，问题就不一样了：K 次串联意味着什么

2.1 读懂编号 1191 的题干

把上一步的经典问题加一个变化：给定数组arr和一个整数k，把arr完整地重复k次，形成新数组，然后求这个新数组的最大子数组和。

这里的k是一道坎。通常题目会把k的上限设到10^9，也就是说你根本不可能真的把数组复制k次。哪怕原数组只有 1000 个元素，k取 10^9，拼接后的数组就有 10^12 个元素，按 4 字节存也要 4TB，这显然不现实。

所以要转换思路：不把数组造出来，而是从数学上推断重复之后的最大子数组和会怎么变化。

2.2 重复数组的内部结构

如果你把arr重复两次，比如arr = [a1, a2, a3]，拼接后是[a1, a2, a3, a1, a2, a3]。在这个长数组里随便选一个连续子数组，你会发现它无非是下面三种情况之一：

1. 完全落在一个副本的内部，比如[a2, a3]。
2. 跨过两个相邻副本的边界，比如第一个副本的[a3]加上第二个副本的[a1, a2]。它本质上等于“第一个副本的一个后缀 + 第二个副本的一个前缀”。
3. 跨过更多副本，比如第一个副本的后缀[a3]，加上中间若干个完整副本，再加上最后一个副本的前缀[a1, a2]。

这个结构非常重要。它告诉我们：不管跨多少副本，任何跨副本的子数组都可以拆成“一段后缀 + 若干个完整数组 + 一段前缀”的组合。

于是我们只需要关注四个量：

• total：整个数组arr的总和
• max_sub：arr内部的最大子数组和
• max_pref：arr的所有前缀和里的最大值
• max_suff：arr的所有后缀和里的最大值

只要把这四个量算出来，答案就能直接推出来，根本不需要真的看拼接后的长数组。

2.3 为什么只需要统计这四个量

有人可能会问，跨副本的时候，为什么中间不是“若干完整数组”的一部分，而是可以拆开考虑？因为数组是循环重复的，每一份副本内容完全一样。如果你把一个跨多副本的子数组拉直，它中间经过的那些完整副本，贡献就是total乘以副本数量。前缀部分就是开头那个副本的前缀，后缀部分就是结尾那个副本的后缀。

那为什么前缀和后缀取“最大值”就够了？因为我们要找的是和最大的子数组，那么前缀当然要挑所有前缀里最大的那一个，后缀也要挑所有后缀里最大的那一个。中间完整副本的数量取决于total的正负，以及k的剩余空间。这样一来，状态量就从“拼接后数组的长度”压缩成了“四个统计量”，问题瞬间简单了。

3. 核心推导：三种情况与一个统一公式

3.1 情况一：k 等于 1，没有跨副本的选项

当k = 1时，数组就是原来的arr，压根不存在“跨副本”这回事。所以答案直接就是max_sub，也就是用 Kadane 算法求出的单副本最大子数组和。

这里最容易犯错的地方是：有人会把k = 1也套到下面的统一公式里，结果得到比真实答案更大的值。原因在于，跨副本结构中的“后缀 + 前缀”需要至少两个副本才存在，k = 1时这个结构不成立。

3.2 情况二：数组总和大于 0，中间完整副本越多越好

如果total > 0，那么每多包含一个完整的arr，子数组的总和就会增加total。既然加的是正数，那当然能加多少就加多少。

假设k非常大，那么最优的跨副本子数组一定是这样选的：

• 从某一个副本里，挑一个和最大的后缀max_suff
• 在它后面，把剩下的所有完整副本都包含进去，也就是(k - 2) * total
• 在最后，再挑一个和最大的前缀max_pref

整体和就是：

max_pref + max_suff + (k - 2) * total

举个例子，arr = [1, -2, 3]，total = 2，max_sub = 3，max_pref = 1，max_suff = 3。当k = 3时，拼接后的数组是[1, -2, 3, 1, -2, 3, 1, -2, 3]，最大子数组其实就是整个数组，和是1 - 2 + 3 + 1 - 2 + 3 + 1 - 2 + 3 = 6。用公式算：1 + 3 + (3 - 2) * 2 = 6，完全吻合。

3.3 情况三：数组总和小于等于 0，中间完整副本不要也罢

如果total <= 0，情况就反过来了。每多包含一个完整副本，反而会把自己的和拉低。所以中间那些完整副本，一个都不要加。

那最多能跨多远？理论上只要跨过一个相邻副本的边界就够了：第一个副本的后缀 + 第二个副本的前缀，也就是max_suff + max_pref。一旦想跨两个边界，中间就必然会夹进至少一个完整副本，反而得不偿失。

举个例子，arr = [1, -5, 1]，total = -3，max_sub = 1，max_pref = 1，max_suff = 1。当k = 10时，拼接后的数组有无数个[1, -5, 1]连在一起。最大子数组只能从某个1开始，跨到下一个副本的1，和是 2。公式算出来也是1 + 1 = 2。

如果数组全是负数，比如[-2, -1, -3]，total < 0，max_sub允许空子数组时为 0，max_pref和max_suff也都为 0，答案就是 0。这对应着“一个元素都不选”的空子数组，和题目约定一致。

3.4 统一成一个公式

把上面三种情况合并一下，对k > 1的情况，答案可以写成：

ans = max(max_sub, max_pref + max_suff + max(0, k - 2) * total)

为什么max(0, k - 2)能同时处理正负total？

• 当total > 0时，我们想让(k - 2) * total尽量大，所以取max(0, k - 2)就是k - 2。
• 当total <= 0时，我们不想加任何负的完整副本，所以让中间的完整副本数量为 0，也就是max(0, k - 2)取 0。

这样用一个式子就把所有k > 1的情况都收进去了。至于k = 1，则单独返回max_sub。

理解这个公式，可以把它想象成一趟列车旅程：max_suff是你从上一站上车的起步段，max_pref是你在终点站下车的收尾段。如果中间每经过一个完整站点都能赚到正的收益（total > 0），那就把能经过的站点全经过；如果中间每站都是亏损（total <= 0），那就只在上车站和下车站之间走最短路，中间一站都不停。

4. 完整代码实现与细节打磨

4.1 Python 参考实现

下面是完整的 Python 实现，可以直接提交：

MOD = 10**9 + 7 class Solution: def kConcatenationMaxSum(self, arr, k): if not arr: return 0 total = sum(arr) # 1. max_sub：经典 Kadane，允许空子数组 cur = best = 0 for x in arr: cur = max(x, cur + x) best = max(best, cur) # 2. max_pref：从左到右扫描，记录前缀和最大 pref = 0 max_pref = 0 for x in arr: pref += x max_pref = max(max_pref, pref) # 3. max_suff：从右到左扫描，记录后缀和最大 suff = 0 max_suff = 0 for x in reversed(arr): suff += x max_suff = max(max_suff, suff) # 4. 分情况合并 if k == 1: ans = best else: ans = max(best, max_pref + max_suff + max(0, k - 2) * total) return ans % MOD

这段代码的时间复杂度是 O(n)，空间复杂度是 O(1)。arr被扫描了几遍，但每遍都是线性的，实际跑起来非常快。

如果要兼容“不允许空子数组”的题目版本，只需要把cur、best、max_pref、max_suff的初始值改成arr[0]或负无穷，然后调整扫描起点即可。思路完全一样。

4.2 前缀最大和与后缀最大和的计算陷阱

很多人写前缀最大值的时候容易写错，原因是把“最大前缀和”理解成了“从任意位置开始到某个位置结束的最大子数组和”。其实不是。

最大前缀和的定义是：必须从数组开头开始，一直加到某个位置，所有可能长度里的最大和。所以它必须从左往右扫，用一个累计变量不断累加，然后记录历史最大值。

最大后缀和的定义是对称的：必须从某个位置开始，一直加到数组末尾。所以它必须从右往左扫。

举一个容易出错的例子：arr = [-1, -2, -3]。如果允许空子数组，最大前缀和是 0（一个都不选），最大后缀和也是 0。如果不允许空子数组，最大前缀和是 -1，最大后缀和是 -3。这两种约定会直接影响到max_pref + max_suff的计算结果，所以动手写代码前一定要先确认题目允不允许空子数组。

4.3 取模与比较大小的顺序问题

这是很多新手必踩的坑。题目要求结果取模10^9 + 7，但比较大小必须在取模之前做。

举个例子，a = 100，b = 2000000000。取模后，a % MOD = 100，b % MOD = 2000000000 - 1000000007 = 999999993，这时候a反而大于b。如果用取模后的值去比大小，会选出错误的“最大值”。

正确做法是：先用原始值算出最大值，最后再对结果取模。上面 Python 代码里的ans % MOD就是放在最后一步。

另外，在 C++ 或 Java 里要小心溢出。k最大到 10^9，total最大也可能到 10^9 甚至更高，两者相乘可能超出 32 位整数范围。所以中间变量要用long long，别省这个细节。

4.4 边界条件与特殊用例

写代码时建议把下面这几个用例在本地跑一遍：

其中[5, -1, 3]是特别好的测试用例：它单数组最大和是 7（整个数组），但重复两次后最大和变成 14（两个整个数组接起来）。如果用“单数组最大和乘以 k”这种错误思路，会得出 14，但那是碰巧对；如果你改成[1, -2, 3]，单数组最大和是 3，重复三次后答案是 6，而3 * 3 = 9，就明显错了。

5. 实战避坑与从这道题学到的 DP 思维

5.1 常见错误速查表

下面这张表是我自己刷题和看别人代码时总结出来的高频错误点，放在这里方便你自查。

5.2 对拍验证方法

如果你的环境允许，可以写一个暴力版本来验证数学推导：当k很小（比如 2 或 3）时，用循环拼接出一个长度不超过几万的数组，然后跑一遍经典 Kadane，再将结果和公式解法对拍。随机生成各种边界数据，比如全正数、全负数、正负交替、总和为正但很多负数、总和恰好为 0 等，对拍几百组都没有问题，基本就能放心提交了。

我自己在做这类题时，习惯先手动算一遍k = 2和k = 3的场景，确认公式没写错，再写代码。千万别小看这一步，它能帮你避免“公式背对了但边界写错了”的尴尬。

5.3 “K 次重复”类题目的通用思路

题目一旦出现“数组重复 K 次”，很容易让人想去真实地构造新数组。但几乎所有的这类题，考察点都在于你能否发现重复结构带来的数学规律。通用的思考路径是：

1. 先考虑k = 1，退化成原始问题；
2. 再考虑k = 2，看看跨一个边界会有什么新情况；
3. 最后考虑total的正负，决定中间完整副本的取舍。

只要把这三步走完，90% 类似的问题都能被拆解掉。比如环形数组最大子数组和，本质上也是“跨边界”的问题，只是它把首尾连成了一个环，处理思路和这里高度相似。

5.4 新手学习路径建议

如果你刚接触动态规划，不要一上来就死磕难题。我的建议是先把经典的最大子数组和刷熟，做到能闭着眼睛写出 Kadane 算法并解释清楚每一步为什么；再做环形数组版本；最后再来挑战这道 K 次串联。每一步都建立在前面一个题之上，思路是递进的。

做题时不要只满足于“会写代码”，要在草稿纸上把状态定义、转移方程、边界条件都写出来。一道题真正吃透的标志，是你能用自己的话把“为什么这样设计状态”讲清楚。1191 这道题最大的价值，就是让你看到 DP 的“状态”不一定要跟着拼接后的数组长度走，有些时候通过数学分析，可以把看起来很大的状态空间压缩到常数级别。

我个人刷完这道题之后的一个习惯是：遇到重复类问题，先画图分析跨边界结构，再动手写代码。最后一个非常实用的小技巧：提交前用k = 2和k = 3的暴力版对拍一下，如果公式解法能稳定通过随机数据测试，那基本就不会有边界漏网了。