模意义下最大子段和

题面

给定长度为 $n$ 的数组 $A = \{a_1, a_2, \dots, a_n\}$ 和模数 $m$ ，求数组 $A$ 模 $m$ 意义下的最大子段和．

形式化地，求：

分析

显然 Kadane 算法不可行．考虑前缀和角度：

设 $S$ 为数组 $A$ 模 $m$ 意义下的前缀和数组，约定 $S_0 = 0$ ．则

固定右端点 $r$ ，根据 $S_r$ 和 $S_{l-1}$ 的大小关系分讨：

1. $S_r \ge S_{l-1}$：
   此时 $(S_r - S_{l-1} + m) \bmod m = S_r - S_{l-1}$ ．
   显然 $S_{l-1}$ 取 $S_0=0$ 时该值最大．此时模意义下子段和 $= S_r$ ．

2. $S_r < S_{l-1}$：
   此时 $(S_r - S_{l-1} + m) \bmod m = S_r - S_{l-1} + m$．
   为使该值最大，则需 $S_{l-1}$ 最小，故 $S_{l-1}$ 应取大于 $S_r$ 的最小值．此时模意义下子段和 $> S_r$ ．

代码实现

暴力枚举复杂度 $O(n^2)$ ．

可利用支持高效插入和查找的数据结构优化“查找最小的大于 $S_r$ 的 $S_{l-1}$”操作．如在 C++ 中可使用基于红黑树的 std::set 实现，单次操作复杂度为 $O(\log n)$．

示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <set>
#include <vector>
using namespace std;
using ll = long long;

ll solve(const vector<ll>& a, ll n, ll m) {
    ll ans = 0, sum = 0;
    set<ll> s;
    s.insert(0);
    for (ll i = 1; i <= n; i++) {
        sum = (sum + a[i] % m + m) % m;
        auto it = s.upper_bound(sum);
        if (it != s.end()) {
            ans = max(ans, sum - *it + m);
        } else {
            ans = max(ans, sum);
        }
        s.insert(sum);
    }
    return ans;
}

复杂度

• 时间复杂度：$O(n \log n)$．
• 空间复杂度：$O(n)$．