双指针
- 两个指针代表子数组的边界(包含)
- 如果区间的和 +a[j] < a[j], 说明区间和为负 此时我们就要移动左边界 i, 这样才有sum增大的可能性,否则继续移动右边界 j 移动过程中保证区间有效 i <= j < n
#include <bits/stdc++.h>
using namespace std;
int a[200002];
int main(){
int n;
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d", &a[i]);
}
int sum=0; // sum 表示区间和
int Max=-102; // 记录sum的最大值
for(int i=0, j=0; i<=j&&j<n;){
if(sum+a[j]>=a[j]){
sum += a[j];
Max = max(sum, Max);
j++;
}
else {
sum -= a[i];
i++;
}
}
printf("%d", Max);
return 0;
}
咳咳,这道题之前见过,这次又遇到还是想了半天,还是有必要记录一下。如有问题,还请指正。