题解 | 最大序列和

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

//给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。
//对于S的所有非空连续子序列T，求最大的序列和。
//变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。

//第一行为一个正整数N，第二行为N个整数，表示序列中的数。

int s[1000001];
int T[1000001];//表示当序列有n个元素时，其最大值。


int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &s[i]);
        }
        T[1] = s[0];
        int currentmax = T[1];
        for (int i = 2; i <= n; i++) {
            if (T[i - 1] <= 0) {
                T[i] = s[i - 1];
            } else {
                T[i] = T[i - 1] + s[i - 1];
            }
            currentmax = max(T[i], currentmax);
        }
        printf("%d\n", currentmax);
    }
    return 0;
}