双指针

  1. 两个指针代表子数组的边界(包含)
  2. 如果区间的和 +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;
}

咳咳,这道题之前见过,这次又遇到还是想了半天,还是有必要记录一下。如有问题,还请指正。