K次串联后最大子数组和

题目描述：
给定一个整数数组arr和一个整数k。将数组重复k次得到新数组，例如arr=[1,2]，k=3，得到新数组[1,2,1,2,1,2]。请找出新数组的最大子数组和（子数组要求是连续的，并且最少包含一个元素）。

解题过程：

1. 问题分析

• 当k=1时，就是经典的最大子数组和问题（Kadane算法）
• 当k>1时，数组被重复了k次，我们需要考虑跨越重复边界的情况
• 关键观察：最大子数组可能出现在单个副本内，也可能跨越多个副本

2. 基础情况分析
   首先我们定义几个关键量：

• total_sum：整个数组arr所有元素的和
• max_prefix：最大前缀和（从数组开头到某个位置的最大和）
• max_suffix：最大后缀和（从某个位置到数组结尾的最大和）
• max_subarray：单个数组内的最大子数组和

3. 分类讨论

情况1：k=1

• 直接使用Kadane算法求最大子数组和

情况2：total_sum ≤ 0

• 如果整个数组的和非正数，那么连接多个副本不会让和变得更大
• 最大子数组和要么在单个副本内，要么跨越两个副本（利用最大后缀+最大前缀）
• 结果为max(max_subarray, max_suffix + max_prefix)

情况3：total_sum > 0

• 数组的和为正数，连接多个副本可以让和变得更大
• 最大子数组可能的结构：最大后缀 + total_sum × (k-2) + 最大前缀
• 结果为max(max_subarray, max_suffix + total_sum × (k-2) + max_prefix)

4. 算法步骤

步骤1：计算单个数组的关键值

def kadane(arr):
    max_ending_here = max_so_far = arr[0]
    for i in range(1, len(arr)):
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

def max_prefix_sum(arr):
    max_sum = curr_sum = 0
    for num in arr:
        curr_sum += num
        max_sum = max(max_sum, curr_sum)
    return max_sum

def max_suffix_sum(arr):
    max_sum = curr_sum = 0
    for num in reversed(arr):
        curr_sum += num
        max_sum = max(max_sum, curr_sum)
    return max_sum

步骤2：根据k的值分类处理

def kConcatenationMaxSum(arr, k):
    n = len(arr)
    total_sum = sum(arr)
    
    # 单个数组内的最大子数组和
    max_sub = kadane(arr)
    
    if k == 1:
        return max(max_sub, 0)
    
    max_pref = max_prefix_sum(arr)
    max_suff = max_suffix_sum(arr)
    
    if total_sum > 0:
        # 正数和情况：可以利用中间完整的(k-2)个副本
        return max(max_sub, max_suff + total_sum * (k - 2) + max_pref, 0)
    else:
        # 非正数和情况：最多跨越两个副本
        return max(max_sub, max_suff + max_pref, 0)

5. 示例验证

示例1：arr=[1,2], k=3

• total_sum=3>0
• max_subarray=3（在单个[1,2]内）
• max_prefix=3, max_suffix=3
• 结果=max(3, 3+3×(3-2)+3)=max(3,9)=9

示例2：arr=[1,-2,1], k=5

• total_sum=0
• max_subarray=1
• max_prefix=1, max_suffix=1
• 结果=max(1, 1+1)=2

6. 时间复杂度分析

• 只需要遍历数组3次（计算Kadane、前缀和、后缀和）
• 时间复杂度：O(n)
• 空间复杂度：O(1)

这个算法巧妙地利用了数组重复的特性，避免了实际构造长度为n×k的新数组，通过数学分析得到了最优解。