如何优化最大子数组和模m代码并降低时间复杂度？

你的原代码逻辑正确，但存在致命的效率问题：

• 时间复杂度为O(n³)：嵌套循环枚举所有子数组（O(n²)），再对每个子数组求和（O(n)），对于n=1e5的大规模数据，子数组数量可达5e9，完全无法处理。
• 空间复杂度为O(n²)：存储了所有子数组，内存占用直接爆炸。

以下是针对大规模数据的核心优化思路：

1. 利用前缀和+模运算性质简化计算 #

首先定义前缀和数组 s，其中：

• s[0] = 0
• s[k] = (a[0] + a[1] + ... + a[k-1]) % m

对于任意子数组 a[i..j]，其和模m的结果等价于：
(s[j+1] - s[i]) % m

根据模运算的性质，这个结果有两种情况：

• 若 s[j+1] > s[i]：结果为 s[j+1] - s[i]
• 若 s[j+1] < s[i]：结果为 s[j+1] + m - s[i]（因为 (s[j+1]-s[i])%m = (s[j+1]-s[i]+m)%m）

我们的目标是找到最大的上述值，其中后者的取值可能更接近m，是潜在的最大值。

2. 用有序数据结构快速查找最优前缀和 #

为了避免遍历所有之前的前缀和（O(n)每次），我们可以维护一个有序的前缀和列表，每次处理当前前缀和时：

• 用二分查找快速找到第一个比当前前缀和大的元素（记为s_x），此时 s_current + m - s_x 是一个候选最大值
• 将当前前缀和插入有序列表，保证后续查找的效率

Python中可以用bisect模块实现这一逻辑，每次二分查找和插入的时间复杂度为O(logn)，整体时间复杂度降至O(n logn)，空间复杂度为O(n)，完全适配大规模数据集。

优化后的代码示例 #

import bisect

def maximumSum(a, m):
    max_mod = 0
    prefix_sum = 0
    sorted_prefix = []
    for num in a:
        # 计算当前前缀和模m
        prefix_sum = (prefix_sum + num) % m
        # 找第一个大于当前前缀和的元素
        idx = bisect.bisect_right(sorted_prefix, prefix_sum)
        if idx < len(sorted_prefix):
            # 计算候选最大值
            current_candidate = (prefix_sum - sorted_prefix[idx] + m) % m
            if current_candidate > max_mod:
                max_mod = current_candidate
        # 检查当前前缀和本身是否为更大值
        if prefix_sum > max_mod:
            max_mod = prefix_sum
        # 将当前前缀和插入有序列表
        bisect.insort(sorted_prefix, prefix_sum)
    return max_mod

关键细节说明 #

• 前缀和提前模m：避免数值溢出，同时不影响最终结果
• 有序列表的作用：将查找符合条件的前缀和的时间从O(n)压缩到O(logn)
• 候选值的两种来源：不仅要考虑跨子数组的模值，还要考虑单个元素或从开头到当前位置的子数组的模值

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