欢迎访问==> 【考研OR保研】机试题
题目描述
给出一个整数序列 $S$,其中有 $N$ 个数,定义其中一个非空连续子序列 $T$ 中所有数的和为 $T$ 的“序列和”。
对于 $S$ 的所有非空连续子序列 $T$,求最大的序列和。
输入格式
第一行包含一个整数 $N$。
第二行包含 $N$ 个整数,表示序列中的元素。
输出格式
输出一个数,表示最大序列和。
数据范围
$1 \\le N \\le 10^6$,
序列中的元素的取值范围 $\[-10^9,10^9\]$。
输入样例1:
5
1 5 -3 2 4
输出样例1:
9
输入样例2:
6
1 -2 3 4 -10 6
输出样例2:
7
输入样例3:
4
-3 -1 -2 -5
输出样例3:
-1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010, INF = 0x3f3f3f3f;
typedef long long ll;
//f[i]表示所有以第i个数为右端点的非空连续子序列的和
//集合划分:将f[i]分为两部分【只包含a[i]】【其他:f[i - 1] + a[i]】
//状态计算:f[i] = max(f[i - 1] + a[i], a[i]);
ll f[N];
int n, a[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++)
{
f[i] = max(f[i - 1], (ll)0) + a[i];
}
ll res = -INF;
for(int i = 1; i <= n; i ++) res = max(res, f[i]);
cout << res << endl;
return 0;
}