记录编号	598238	评测结果	AAAAAAAAAA
题目名称	82.单子序列最大和	最终得分	100
用户昵称	zhm	是否通过	通过
代码语言	C++	运行时间	0.053 s
提交时间	2025-01-23 10:09:03	内存使用	1.72 MiB

#include <cstdio>
#include <algorithm>
 
const int N = 1e6;
 
int s[N+5], smin[N+5];
 
int main(void)
{
	freopen("subq.in", "r", stdin);
	freopen("subq.out", "w", stdout);
	int n;
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++) {
		scanf("%d", &s[i]);
		s[i] += s[i - 1];
	}
	
	smin[1] = 0;
	for (int i = 2; i <= n; i++) {
		if (s[smin[i - 1]] > s[i - 1]) smin[i] = i - 1;
		else smin[i] = smin[i - 1];
	}
	int ans = -0x3fffffff, l = 0x3fffffff, r;
	for (int i = 1; i <= n; i++) {
		if (ans < s[i] - s[smin[i]]) {
			ans = s[i] - s[smin[i]];
			l = smin[i] + 1;
			r = i;
		} else if (ans == s[i] - s[smin[i]] && smin[i] < l)
			l = smin[i], r = i;
	}
	printf("%d\n%d\n%d\n", l, r, ans);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}