# 最大子段和## 题目描述给定一个长为 $n$ 的序列任意选择其中连续的 $x$$0le xle n$项所确定的一段更短的连续序列叫作一个子段。一个子段的得分为其每个元素之和请求出原序列的最大子段和。## 输入格式从标准输入读入数据。第一行一个正整数 $n$$1le nle 10^6$代表序列长度。第二行输入 $n$ 个整数 $a_i$$lefta_irightle10^6$为序列元素。## 输

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int a[N], s[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    int res = -1e9, ans = -1e9;
    for (int i = 1; i <= n; i ++ )
    {
        s[i] = s[i - 1] + a[i];
        res = max(res, s[i - 1]);
        ans = max(ans, s[i] - res);
    }

    printf("%d\n", ans);

    return 0;
}