线性动态规划：K次串联后最大子数组和

题目描述
给定一个长度为 n 的整数数组 arr 和一个整数 k，将数组重复 k 次得到新数组 arr * k（例如 arr = [1, 2]，k = 3 时新数组为 [1, 2, 1, 2, 1, 2]）。求新数组中连续子数组的最大和（子数组可以为空，此时和为 0）。

示例

• 输入：arr = [1, -2, 1], k = 5
• 输出：2
• 解释：最大和子数组为 [1, 1]（取自串联后的第 2 个 1 和第 3 个 1）。

解题思路

步骤 1：分析问题关键

1. 串联后的数组长度为 n * k，若直接模拟串联后求解最大子数组和（用 Kadane 算法），时间复杂度为 O(n*k)，在 k 很大时（如 k=10^5）会超时。
2. 核心观察：
   • 若 k=1，直接求原数组的最大子数组和。
   • 若 k>1，最大和可能来自：
     • 单个周期内的最大子数组和（即 k=1 的结果）。
     • 跨周期的子数组，需结合数组的前缀最大和、后缀最大和和整个数组的和。

步骤 2：定义关键变量

设：

• maxSub：单个周期内最大子数组和（允许为空，最小为 0）。
• totalSum：整个数组 arr 所有元素的和。
• prefixMax：前缀最大和（从数组开头到某个位置的最大和，从左到右累加）。
• suffixMax：后缀最大和（从数组末尾到某个位置的最大和，从右到左累加）。

步骤 3：分情况讨论

1. k=1：直接返回 maxSub。
2. k>=2：最大和可能为：
   • 情况 1：单个周期内的 maxSub。
   • 情况 2：跨两个周期，即 suffixMax + prefixMax（最后一个周期的后缀最大和 + 第一个周期的前缀最大和）。
   • 情况 3：跨多个周期，若 totalSum > 0，则最大和可能为 suffixMax + (k-2)*totalSum + prefixMax（中间周期全部取用）。

步骤 4：动态规划计算

1. 计算单个周期的 maxSub（Kadane 算法）：

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

2. 计算 prefixMax：

   prefixMax = [0] * n  
   cur = 0  
   for i in range(n):  
       cur += arr[i]  
       prefixMax[i] = max(prefixMax[i-1] if i>0 else 0, cur)  
   

3. 计算 suffixMax：

   suffixMax = [0] * n  
   cur = 0  
   for i in range(n-1, -1, -1):  
       cur += arr[i]  
       suffixMax[i] = max(suffixMax[i+1] if i<n-1 else 0, cur)  
   

步骤 5：合并结果

• 若 k=1：结果 = maxSub。
• 若 k>=2：

  候选1 = maxSub  
  候选2 = suffixMax[0] + prefixMax[-1]  # 跨两个周期  
  候选3 = suffixMax[0] + (k-2)*totalSum + prefixMax[-1]  # 跨所有周期（仅当 totalSum>0 时有效）  
  结果 = max(候选1, 候选2, 候选3)  
  

  注意：若 totalSum <= 0，则候选3无效，只需比较候选1和候选2。

示例演算

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

1. 单个周期 maxSub：
   • Kadane 过程：
     • x=1: cur=1, maxSub=1
     • x=-2: cur=max(-2, 1-2)=-1, maxSub=1
     • x=1: cur=max(1, -1+1)=1, maxSub=1
   • maxSub=1
2. totalSum = 1 + (-2) + 1 = 0
3. prefixMax：
   • i=0: cur=1, prefixMax[0]=1
   • i=1: cur=1-2=-1, prefixMax[1]=max(1, -1)=1
   • i=2: cur=0, prefixMax[2]=max(1,0)=1
4. suffixMax：
   • i=2: cur=1, suffixMax[2]=1
   • i=1: cur=1-2=-1, suffixMax[1]=max(1, -1)=1
   • i=0: cur=1, suffixMax[0]=max(1,1)=1
5. 因 k=5>=2，且 totalSum=0：
   • 候选1=1
   • 候选2=suffixMax[0]+prefixMax[2]=1+1=2
   • 候选3无效（因 totalSum<=0）
   • 结果=max(1,2)=2 ✅

复杂度分析

• 时间复杂度：O(n)，仅遍历数组常数次。
• 空间复杂度：O(n)，存储前缀/后缀数组。

总结：通过分解串联后的数组为周期，利用周期性和子数组和的性质，避免直接处理长数组，将问题优化到线性时间解决。