动态规划入门绕不开“最大子数组和”这道题本身有很经典的 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^6O(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]。在这个长数组里随便选一个连续子数组你会发现它无非是下面三种情况之一完全落在一个副本的内部比如[a2, a3]。跨过两个相邻副本的边界比如第一个副本的[a3]加上第二个副本的[a1, a2]。它本质上等于“第一个副本的一个后缀 第二个副本的一个前缀”。跨过更多副本比如第一个副本的后缀[a3]加上中间若干个完整副本再加上最后一个副本的前缀[a1, a2]。这个结构非常重要。它告诉我们不管跨多少副本任何跨副本的子数组都可以拆成“一段后缀 若干个完整数组 一段前缀”的组合。于是我们只需要关注四个量total整个数组arr的总和max_subarr内部的最大子数组和max_prefarr的所有前缀和里的最大值max_suffarr的所有后缀和里的最大值只要把这四个量算出来答案就能直接推出来根本不需要真的看拼接后的长数组。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 2max_sub 3max_pref 1max_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 -3max_sub 1max_pref 1max_suff 1。当k 10时拼接后的数组有无数个[1, -5, 1]连在一起。最大子数组只能从某个1开始跨到下一个副本的1和是 2。公式算出来也是1 1 2。如果数组全是负数比如[-2, -1, -3]total 0max_sub允许空子数组时为 0max_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 100b 2000000000。取模后a % MOD 100b % MOD 2000000000 - 1000000007 999999993这时候a反而大于b。如果用取模后的值去比大小会选出错误的“最大值”。正确做法是先用原始值算出最大值最后再对结果取模。上面 Python 代码里的ans % MOD就是放在最后一步。另外在 C 或 Java 里要小心溢出。k最大到 10^9total最大也可能到 10^9 甚至更高两者相乘可能超出 32 位整数范围。所以中间变量要用long long别省这个细节。4.4 边界条件与特殊用例写代码时建议把下面这几个用例在本地跑一遍测试用例k预期结果[1, 2]1030[-1, -2, -3]50[1, -5, 1]102[1, -2, 3]13[5, -1, 3]17[5, -1, 3]214其中[5, -1, 3]是特别好的测试用例它单数组最大和是 7整个数组但重复两次后最大和变成 14两个整个数组接起来。如果用“单数组最大和乘以 k”这种错误思路会得出 14但那是碰巧对如果你改成[1, -2, 3]单数组最大和是 3重复三次后答案是 6而3 * 3 9就明显错了。5. 实战避坑与从这道题学到的 DP 思维5.1 常见错误速查表下面这张表是我自己刷题和看别人代码时总结出来的高频错误点放在这里方便你自查。错误现场根本原因正确做法直接把数组重复 k 次再 Kadanek 太大空间和时间都爆用 four-fold 统计量做数学推导不真拼接k 1 时套统一公式跨副本结构至少需要两个副本k 1 时单独返回 max_sub比较大小前先取模取模会改变大小关系先取 max最后统一取模max_pref 或 max_suff 写成负无穷题目允许空子数组答案最小是 0初始化为 0total 为正时忘记加 (k-2)*total忽略了完整副本的贡献统一用 max(0, k-2) * totaltotal 为负时还加 (k-2)*total负的完整副本会拉低答案让中间完整副本数量取 0后缀最大和用从左往右扫后缀必须包含末尾方向反了从右往左扫描累计5.2 对拍验证方法如果你的环境允许可以写一个暴力版本来验证数学推导当k很小比如 2 或 3时用循环拼接出一个长度不超过几万的数组然后跑一遍经典 Kadane再将结果和公式解法对拍。随机生成各种边界数据比如全正数、全负数、正负交替、总和为正但很多负数、总和恰好为 0 等对拍几百组都没有问题基本就能放心提交了。我自己在做这类题时习惯先手动算一遍k 2和k 3的场景确认公式没写错再写代码。千万别小看这一步它能帮你避免“公式背对了但边界写错了”的尴尬。5.3 “K 次重复”类题目的通用思路题目一旦出现“数组重复 K 次”很容易让人想去真实地构造新数组。但几乎所有的这类题考察点都在于你能否发现重复结构带来的数学规律。通用的思考路径是先考虑k 1退化成原始问题再考虑k 2看看跨一个边界会有什么新情况最后考虑total的正负决定中间完整副本的取舍。只要把这三步走完90% 类似的问题都能被拆解掉。比如环形数组最大子数组和本质上也是“跨边界”的问题只是它把首尾连成了一个环处理思路和这里高度相似。5.4 新手学习路径建议如果你刚接触动态规划不要一上来就死磕难题。我的建议是先把经典的最大子数组和刷熟做到能闭着眼睛写出 Kadane 算法并解释清楚每一步为什么再做环形数组版本最后再来挑战这道 K 次串联。每一步都建立在前面一个题之上思路是递进的。做题时不要只满足于“会写代码”要在草稿纸上把状态定义、转移方程、边界条件都写出来。一道题真正吃透的标志是你能用自己的话把“为什么这样设计状态”讲清楚。1191 这道题最大的价值就是让你看到 DP 的“状态”不一定要跟着拼接后的数组长度走有些时候通过数学分析可以把看起来很大的状态空间压缩到常数级别。我个人刷完这道题之后的一个习惯是遇到重复类问题先画图分析跨边界结构再动手写代码。最后一个非常实用的小技巧提交前用k 2和k 3的暴力版对拍一下如果公式解法能稳定通过随机数据测试那基本就不会有边界漏网了。