因為都是正整數,所以滑動視窗O(n)即可,令右界和左界一一往後推就好了
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector <int> v(n);
for (auto &i:v){
cin >> i;
}
//l=左界, r=右界
int l=0, ans=0, sum=0;
for (int r=0; r<n; r++){
sum+=v[r];
//對於每個右界,若移動後加總大於k則縮減左界
while(sum>k){
sum-=v[l];
l++;
}
//for+while 看起來O(n^2)但是l, r都只會掃過去一次所以是O(n)
ans=max(ans, sum);
}
cout << ans << '\n';
}