数组区间最大和模M问题求解及计数（复杂度需低于O(N²)）

这是个经典的数组区间模最值问题，要求复杂度低于O(N²)，核心思路确实是用前缀和模M来转化问题，下面我一步步拆解：

问题描述 #

给定数组A = [a₀,a₁,…,aₙ]，长度N ≤ 10^5，元素满足0 ≤ aᵢ ≤ 10^9；给定整数0 < M ≤ 10^9。需要找到区间[i,j]的元素和∑(k=i到j)aₖ mod M的最大值，并统计能达到该最大值的不同区间[i,j]的数量，要求算法复杂度低于O(N²)。
示例：N=3，M=5，A={2,4,3}，最大模和为4，对应2个区间：[0,2]（a₀到a₂）、[1,1]（a₁）。

核心思路 #

利用前缀和模M将区间和转化为前缀和的差值模M，把暴力枚举问题转化为有序集合的高效查询问题：

1. 定义前缀和s[j] = (a₀ + a₁ + ... + aⱼ) mod M，同时引入初始前缀和s_initial = 0（对应空区间，用于计算从数组开头到j的区间和）；
2. 区间[i,j]的和模M可表示为(s[j] - s[i-1]) mod M，其中s[i-1]是i-1位置的前缀和（i=0时取s_initial=0）；
3. 这个模值有两种关键情况：
   • 若s[j] ≥ s[i-1]，模值为s[j] - s[i-1]，最大值为s[j]（对应s[i-1]=0的情况，也就是从数组开头到j的区间）；
   • 若s[j] < s[i-1]，模值为s[j] + M - s[i-1]，这个值会大于s[j]，要最大化它，需要找到大于s[j]的最小前缀和（因为s[i-1]越小，M - (s[i-1]-s[j])越大）；
4. 维护一个有序集合记录已遍历的前缀和及其出现次数，快速查询目标前缀和并统计区间数量。

具体实现步骤 #

1. 计算前缀和数组 #

遍历数组，依次计算每个位置的前缀和模M，得到长度为N的数组s。

2. 初始化有序集合 #

初始时集合中包含0，计数为1（对应初始前缀和s_initial）。可以用有序列表配合二分查找（如Python的bisect模块），或平衡树结构（如Java的TreeMap）。

3. 遍历前缀和，更新最大值与计数 #

对于每个s[j]：

• 计算候选最大值：
  • 候选1：s[j]，对应所有s[i-1]=0的区间（从数组开头到j的区间，或其他前缀和为0的位置开始的区间）；
  • 候选2：通过二分查找找到有序集合中大于s[j]的最小元素x，若存在则计算(s[j] + M - x)，否则候选2不存在；
• 更新全局最大值和计数：
  • 若候选2存在且大于候选1：
    • 若候选2 > 当前global_max：更新global_max为候选2，计数设为x的出现次数；
    • 若候选2 == 当前global_max：将x的出现次数加到计数中；
  • 若候选1更大或候选2不存在：
    • 若候选1 > 当前global_max：更新global_max为候选1，计数设为集合中0的出现次数；
    • 若候选1 == 当前global_max：将集合中0的出现次数加到计数中；
• 将当前s[j]加入集合：若集合中已有s[j]则计数加1，否则添加新条目并保持集合有序。

4. 复杂度分析 #

• 前缀和计算：O(N)；
• 每个前缀和的二分查询与插入：O(log N)，总复杂度为O(N log N)，满足低于O(N²)的要求。

代码示例（Python） #

import bisect

def max_mod_sum_and_count(A, M):
    prefix_mod = []
    current_sum = 0
    for num in A:
        current_sum = (current_sum + num) % M
        prefix_mod.append(current_sum)
    
    sorted_list = [0]
    count_map = {0: 1}
    global_max = 0
    total_count = 0
    
    for s in prefix_mod:
        # 查找大于s的最小元素
        idx = bisect.bisect_right(sorted_list, s)
        candidate2 = -1
        cnt2 = 0
        if idx < len(sorted_list):
            x = sorted_list[idx]
            candidate2 = (s + M - x) % M
            cnt2 = count_map[x]
        
        # 候选1为s，对应前缀和为0的区间数量
        candidate1 = s
        cnt1 = count_map.get(0, 0)
        
        current_max = max(candidate1, candidate2)
        if current_max > global_max:
            global_max = current_max
            total_count = 0
            if candidate1 == current_max:
                total_count += cnt1
            if candidate2 == current_max:
                total_count += cnt2
        elif current_max == global_max:
            if candidate1 == current_max:
                total_count += cnt1
            if candidate2 == current_max:
                total_count += cnt2
        
        # 将当前s加入集合
        if s in count_map:
            count_map[s] += 1
        else:
            count_map[s] = 1
            bisect.insort(sorted_list, s)
    
    return global_max, total_count

# 测试示例
A = [2,4,3]
M = 5
print(max_mod_sum_and_count(A, M))  # 输出(4, 2)，符合预期

注意事项 #

• 初始前缀和0必须加入集合，否则会漏掉从数组开头开始的区间；
• 当多个前缀和相同时，要正确统计出现次数，避免重复或遗漏区间；
• 当所有前缀和都为0时，最大模和为0，区间数量为N*(N+1)//2，代码会自动正确计算。

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