求首尾元素相等的最大连续子数组和的高效解法

暴力解法需要枚举所有首尾相等的子数组计算和，时间复杂度为O(n²)，以下是时间复杂度O(n)、空间复杂度*O(n)*的优化方案：

核心思路 #

• 利用前缀和简化子数组和计算：设preSum[i]为数组前i个元素（下标0到i-1）的累加和，那么下标从l到r的连续子数组和为preSum[r+1] - preSum[l]
• 我们需要满足arr[l] = arr[r]，要最大化上述子数组和，等价于对于每个右边界r，找到所有满足arr[l] = arr[r]的l中，最小的preSum[l]
• 用哈希表存储每个数值对应的最小preSum[l]，遍历数组时同步更新哈希表和最大和即可

边界处理 #

单个元素也是符合首尾相等要求的子数组，因此最大和的初始值设为数组的最大元素值，避免数组全为负数时结果错误。

代码实现（Python） #

def max_equal_end_subarray_sum(arr):
    from collections import defaultdict
    max_sum = max(arr) # 初始化单个元素的最大值
    pre_sum = 0
    # 哈希表存储每个数值对应的最小pre_sum值
    min_pre_map = defaultdict(lambda: float('inf'))
    
    for num in arr:
        if min_pre_map[num] != float('inf'):
            # 计算当前子数组和
            current_sum = pre_sum + num - min_pre_map[num]
            if current_sum > max_sum:
                max_sum = current_sum
        # 更新当前数值对应的最小pre_sum
        if pre_sum < min_pre_map[num]:
            min_pre_map[num] = pre_sum
        # 前缀和累加当前元素
        pre_sum += num
    return max_sum

示例验证 #

• 示例1输入：[1,9,-2,9,4,2,4]，输出：16，对应子数组[9,-2,9]
• 示例2输入：[9,-18,9,2,9]，输出：20，对应子数组[9,2,9]
• 示例3输入：[5,1,4,1,10,1,7]，输出：17，对应子数组[1,4,1,10,1]

内容的提问来源于stack exchange，提问作者Kirti Kedia