ZYF001 区间最大和
大约 1 分钟
ZYF001 区间最大和
【算法】 双指针、滑动窗口
【C++】 双指针、前缀和
【难度】 普及−
一、题目简述
个正整数,找一个子区间 ,使得和在不超过 的情况下最大。如有多个,输出 最小的。
二、解题思路
双指针(滑动窗口):维护 和当前窗口和 。
- 不断右移, 累加
- 当 时, 右移直到
- 每步更新最大和及对应区间
由于元素都是正整数,窗口越大和越大,这个贪心正确。
手动模拟 [2,3,4,5,6], m=10:
- l=1,r=1: sum=2, ans=2, 区间[1,1]
- l=1,r=2: sum=5, ans=5, 区间[1,2]
- l=1,r=3: sum=9, ans=9, 区间[1,3]
- l=1,r=4: sum=14>10 → l++ → sum=12>10 → l++ → sum=9, l=3,r=4, ans=9
- l=3,r=5: sum=15>10 → l++ → sum=11>10 → l++ → sum=6, l=5,r=5
- 最终:区间[1,3], 和=9
注意:当有多个区间和等于最大和时,取 最小的。由于 从小到大移动,先找到的区间就是 最小的。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
int l = 1, sum = 0;
int bestSum = 0, bestL = 1, bestR = 0;
for (int r = 1; r <= n; r++) {
sum += a[r];
while (sum > m && l <= r) {
sum -= a[l];
l++;
}
// 区间 [l, r] 的和 <= m
if (sum > bestSum) {
bestSum = sum;
bestL = l;
bestR = r;
}
}
cout << bestL << " " << bestR << " " << bestSum << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。每个元素最多进出窗口一次。
- 空间复杂度: 额外空间(不计输入数组)。
