区间最大和
题目描述：给定 n 个正整数组成的数列 a1,a2,⋯,an 和一个整数 m。求出这个数列中的一个子区间 [i,j]，也就是在这个数列中连续的数字 ai,ai+1,⋯,aj−1,aj，使得这个子区间的和在不超过 m 的情况下最大。如果有多个区间符合要求，请输出 i 最小的那一个。
#include <bits/stdc++.h>
using namespace std;
long long s[4000001];
int main()
{
int n, m, a;
int ans = -1, ai = -1, aj = -1;
scanf("%d%d", &n, &m);
s[0] = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a);
s[i] = s[i - 1] + a;
}
for (int i = 1; i < n; i++)
{
//时间复杂度过高
//因为前缀和单调递增，所以用二分寻找合理的j
long long t = s[i - 1] + m;
long long *p = upper_bound(s + 1 + i, s + 1 + n, t); //第一个大于的位置
//因为p指向的位置刚好大于t，所以要小于等于t必须p-1
if (s[p - s - 1] - s[i - 1] > ans)
{
ans = s[p - s - 1] - s[i - 1];
ai = i;
aj = p - s - 1;
}
}
printf("%d %d %d\n", ai, aj, ans);
return 0;
}
值得注意的是，前缀和数组一定是一个单调不降的数组。因此可以通过二分的所有手段来提高查找的效率。