如何优化「区间最大求和值」问题的Python代码？

需求说明 #

给定整数列表A，针对ranges列表中的每对(首索引, 尾索引)，计算A中该区间（首尾均包含）的元素和，返回所有和中的最大值。

示例：

A = [1, -2, 3, 4, -5, -4, 3, 2, 1]
ranges = [(1, 3), (0, 4), (6, 8)]
# 结果：6（对应区间(6,8)的和：3+2+1=6）

注意事项：

• ranges列表非空；
• 整数列表A最多含100000个元素，ranges列表最多含10000个元素。

原代码的问题 #

原代码时间复杂度为O(M*N)（M是ranges的数量，N是区间平均长度），面对大规模数据会出现严重性能瓶颈：

• 每个区间需两次遍历（先收集索引再求和），冗余操作多；
• 额外存储索引列表，增加不必要的内存开销。

优化方案：前缀和数组 #

利用前缀和数组可将区间求和的时间复杂度从O(N)降至O(1)，整体时间复杂度优化为O(n + m)（n是A的长度，m是ranges的数量），完全适配大规模数据计算。

前缀和原理

定义前缀和数组prefix：

• prefix[0] = 0
• prefix[i] = A[0] + A[1] + ... + A[i-1]

对于区间[l, r]（首尾均包含），其元素和为：prefix[r+1] - prefix[l]

优化后的代码

def max_sum(a, ranges):
    # 构建前缀和数组
    prefix = [0] * (len(a) + 1)
    for i in range(len(a)):
        prefix[i+1] = prefix[i] + a[i]
    
    max_val = float('-inf')
    for l, r in ranges:
        current_sum = prefix[r+1] - prefix[l]
        if current_sum > max_val:
            max_val = current_sum
    return max_val

优化点说明 #

1. 时间效率：前缀和仅需一次O(n)预处理，后续每个区间求和都是O(1)的减法操作，10000个区间仅需10000次计算；
2. 内存效率：无需存储所有区间和，直接跟踪最大值，避免了存储10000个整数的额外开销；
3. 代码简洁性：去掉原代码中冗余的索引收集步骤，逻辑更清晰。

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