洛谷题单指南-常见优化技巧-P1115 最大子段和

原题链接：https://www.luogu.com.cn/problem/P1115

题意解读：最大连续子序列的和。

解题思路：

DP的做法可参考：https://www.cnblogs.com/jcwy/p/18144124

也可以采用双指针来枚举：

i从1开始，j=i

用j来枚举连续序列，如果已有序列和+下一个a[j] >= 下一个a[j]，那个j一直++，累加序列和

如果出现已有序列和+下一个a[j] < 下一个a[j]，那么i跳到j的位置，重复上述过程

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
int n;
int a[N];
int ans = INT_MIN;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        int j = i;
        while(sum + a[j] >= a[j] && j <= n)
        {
            sum += a[j];
            ans = max(ans, sum);
            j++;
        }
        if(j > n) break;
        if(sum + a[j] < a[j])
        {
            sum = 0;
            i = j - 1;
        }
    }
    cout << ans;
    return 0;
}