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

【算法题解】重复数组的最大子数组和问题（kConcatenationMaxSum）

题目描述

给定一个整数数组 arr 和一个整数 k，通过将数组 arr 重复 k 次来生成一个新的数组。例如：

• 如果 arr = [1, 2]，k = 3，
• 那么新数组为 [1, 2, 1, 2, 1, 2]。

要求：
返回新数组中最大子数组的和 。
其中，子数组长度可以为0，空子数组的和定义为0。
由于结果可能非常大，要求返回值对 10^9 + 7 取模。

解题分析

此题的核心是利用数组重复带来的结构特性，求最大子数组和。

1. 朴素思路：直接拼接数组，计算最大子数组和

最直观的做法是将数组重复 k 次，得到长度为 n * k 的大数组，再用经典的 Kadane 算法求最大子数组和。

• 复杂度高，特别当 k 很大时（可能高达 10^5），此方法不可行。

2. 优化思路

观察问题可发现：

• 最大子数组和问题（Kadane算法） ：
  计算一个数组的最大子数组和的经典方法，时间复杂度 O(n)。

• 重复数组的特性 ：
  新数组由原数组连续重复拼接形成，子数组可能跨越多个原数组边界。

• 整体数组和影响 ：
  设 total_sum = sum(arr)。

• • 若 total_sum <= 0，重复越多，中间数组和的累积不会带来收益，最大子数组和一般出现在连续的1到2次拼接的数组内。
  • 若 total_sum > 0，中间完整的 arr 片段对最大子数组和贡献显著，且随着 k 增大，最大子数组和会线性增长。

具体解题方法

1. 计算单个数组最大子数组和

用 Kadane 算法快速计算 arr 的最大子数组和，记为 max_sub_sum。

2. 计算前缀最大和和后缀最大和

• 前缀最大和**max_prefix_sum**：
  从数组开始位置起，连续元素和的最大值。

• 后缀最大和**max_suffix_sum**：
  从数组末尾向前，连续元素和的最大值。

这两个值用于跨边界拼接的子数组计算。

3. 计算两次拼接数组的最大子数组和

对数组重复两次 arr * 2 用 Kadane 算法求最大子数组和，记为 max_sub_sum_two。

考虑两次拼接可以覆盖跨边界的子数组。

4. 根据数组总和 total_sum 判断结果

如果**total_sum <= 0**，最大子数组和不会因为重复多次而变大，结果为：

• max⁡(0,max_sub_sum_two)

如果**total_sum > 0**，中间 k-2 段完整数组可以累计贡献大量正和，最大子数组和为：

• max⁡(max_sub_sum_two,max_suffix_sum+(k−2)×total_sum+max_prefix_sum)

代码实现（Python）

 from typing import List

    
  
    
 class Solution:
    
     def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
    
     MOD = 10**9 + 7
    
     
    
     # Kadane算法，求最大子数组和，允许空子数组，返回非负值
    
     def kadane(nums):
    
         max_ending_here = max_so_far = 0
    
         for x in nums:
    
             max_ending_here = max(0, max_ending_here + x)
    
             max_so_far = max(max_so_far, max_ending_here)
    
         return max_so_far
    
     
    
     total_sum = sum(arr)
    
     max_sub_sum = kadane(arr)
    
     
    
     if k == 1:
    
         return max_sub_sum % MOD
    
     
    
     # 计算前缀最大和
    
     max_prefix_sum = curr = 0
    
     for x in arr:
    
         curr += x
    
         max_prefix_sum = max(max_prefix_sum, curr)
    
     
    
     # 计算后缀最大和
    
     max_suffix_sum = curr = 0
    
     for x in reversed(arr):
    
         curr += x
    
         max_suffix_sum = max(max_suffix_sum, curr)
    
     
    
     max_sub_sum_two = kadane(arr * 2)
    
     
    
     if total_sum <= 0:
    
         result = max(max_sub_sum_two, 0)
    
     else:
    
         result = max(max_sub_sum_two, max_suffix_sum + (k - 2) * total_sum + max_prefix_sum)
    
     
    
     return result % MOD
    
    
    
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-16/Fr7aSkqYAuGoh5mn4dZJNKX1pOyw.png)

复杂度分析

• 时间复杂度：

• • Kadane算法对长度为 n 的数组是 O(n)。
  • 两倍数组长度是 2n，依然是 O(n)。
  • 总共执行常数次 Kadane，复杂度为 O(n)。

• 空间复杂度：

• • 只使用常数额外空间，空间复杂度 O(1)。

示例说明

示例 1

输入：
arr = [1, 2]，k = 3

生成数组：
[1, 2, 1, 2, 1, 2]

• 单次最大子数组和 = 3 (子数组 [1,2])
• 总和 = 3， > 0
• 前缀最大和 = 3
• 后缀最大和 = 3
• 两倍数组最大子数组和 = 6 (子数组 [1, 2, 1, 2])

计算公式：

• max⁡(6,3+(3−2)×3+3)=max⁡(6,3+3+3)=9

输出：
9

示例 2

输入：
arr = [-1, -2]，k = 3

生成数组：
[-1, -2, -1, -2, -1, -2]

• 单次最大子数组和 = 0 （空子数组）
• 总和 = -3 ≤ 0
• 两倍数组最大子数组和 = 0
• 结果为 max(0,0) = 0

输出：
0

总结

本题利用了 Kadane 算法和前缀/后缀和的思想，将数组重复多次的问题拆解为少数几次计算，大大提升了效率。

• 关键在于判断数组总和对结果的影响，分情况处理。
• 如果总和为负或零，最多考虑两倍数组长度的情况。
• 如果总和为正，中间完整段可累积贡献。
• 允许空子数组，确保返回非负最大值。

该思路也适用于类似的重复数组求最大和问题，掌握后能够快速应对相关变体。