• 当然还有更简单的做法
• 设 $now[i]$ 表示 $a[i..n]$ 的和
• 那么 $now[l - 1] - now[r]$ 表示子数组 $a[l..r]$ 的和
• 假设要计算以 $a[i]$ 为起点的子数组中有多少个为 $0$
• 相当于要看 $now[i + 1], now[i + 1], \cdots, now[n]$ 中有多少个等于 $now[i]$
• 那么我们从后往前做，用 map 维护 $now[i]$ 就好

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		vector<int> a(n + 1);
		for (int i = 1; i <= n; i++) cin >> a[i];
		
		i64 ans = 0;
		
		// now[i]: a[i..n] 的和 
		// 那么 now[l - 1] - now[r] 表示子数组 a[l..r] 的和
		vector<i64> now(n + 2, 0);

		// q 对 now 里面的值计数
		map<i64, i64> q;
		q[0] = 1;
		for (int i = n; i >= 1; i--) {
			
			// 以 a[i] 为起点的 2 个后缀相减
			// 得到一段以 a[i] 为起点的子数组
			now[i] = now[i + 1] + a[i];

			// 要计算以 a[i] 为起点的子数组有多少个为 0
			// 也就是说要看 q 中有多少个 now[i]
			ans = max(ans, q[now[i]]);

			// 统计完后把 now[i] 插入 q
			q[now[i]]++;
		}
		cout << ans << '\n';
	}
	return 0;
}

• 从后往前维护后缀

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		vector<int> a(n + 1);
		for (int i = 1; i <= n; i++) cin >> a[i];

		// tmp: 全局标记, q 中的数 + tmp 后才是实际的值
		i64 tmp = 0, ans = 0;
		map<i64, i64> q;
		for (int i = n; i >= 1; i--) {
			// 所有数 + a[i], 直接更新全局标记
			tmp += a[i];

			// 新增一个数 a[i]
			// 插入 q 的数其实是 a[i] - tmp
			q[a[i] - tmp]++;

			// 查询 0 的个数, 就是 q 中 0 - tmp 的个数
			if (q.count(0 - tmp)) ans = max(ans, q[0 - tmp]);
		}
		cout << ans << '\n';
	}
	return 0;
}


/*
2
5
-1 0 1 0 0
5
4 2 0 -2 9
*/

• 从前往后维护后缀

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		vector<int> a(n + 1);
		for (int i = 1; i <= n; i++) cin >> a[i];
		
		i64 tmp = 0;
		map<i64, int> q;
		for (int i = 1; i <= n; i++) {
			// tmp 是 a[0..i] 的前缀和
			tmp += a[i];
			
			// q 里存储不同前缀和计数
			q[tmp]++;
		}
		
		tmp = 0;
		int ans = (q.count(0) ? q[0] : 0);
		for (int i = 2; i <= n; i++) {
			// q 里本来存储的是 从 i - 1 开始的前缀和
			// 而现在要查询从 i 开始的前缀和
			// 不用全部修改, 可以维护一个偏移量 tmp
			tmp += a[i - 1];
			ans = max(ans, --q[tmp]);
			if (q[tmp] == 0) q.erase(tmp);
		}
		cout << ans << '\n';
	}
	return 0;
}


/*
2
5
-1 0 1 0 0
5
4 2 0 -2 9
*/