【题目描述】
给出一个长度为 n n n的序列 a a a，选出其中连续且非空的一段使得这段和最大。

【输入格式】
第一行是一个整数，表示序列的长度 n n n。
第二行有 n n n个整数，第 i i i个整数表示序列的第 i i i个数字 a i a_i ai​。

【输出格式】
输出一行一个整数表示答案。

【数据范围】
1 ≤ n ≤ 2 × 1 0 5 , − 1 0 4 ≤ a i ≤ 1 0 4 1\leq n\leq 2×10^5,-10^4\leq a_i\leq 10^4 1≤n≤2×105,−104≤ai​≤104

【输入样例】

7
2 -4 3 -1 2 -4 3

【输出样例】

4

【代码】

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

const int N = 200010;
int a[N], f[N];//f[i]表示以i结尾的连续区间，f[i] = max(f[i - 1] + a[i], a[i])
int n;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int res = -0x3f3f3f3f;
	for (int i = 1; i <= n; i++)
	{
		f[i] = max(f[i - 1], 0) + a[i];
		res = max(res, f[i]);
	}
	cout << res << endl;
	return 0;
}