题解 | #最大序列和#

因为题目要求连续，所以只能从相邻的状态转移过来。 改一下最长上升子序列这道题的转移方程就可以了

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1000000 + 10;

int n;
int a[N];
int f[N];

int main()
{
    while (cin >> n)
    {
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        f[1] = a[1];
        for (int i = 2; i <= n; ++i)
        {
            f[i] = a[i];
            f[i] = max(f[i], f[i-1] + a[i]);
        }
        int res = -0x3f3f3f3f;
        for (int i = 1; i <= n; ++i)
            res = max(res, f[i]);
        printf("%d\n", res);
    }
    return 0;
}