题目描述

给定一个长度为 $n$ 的整数序列，请选择一个连续且非空的子段，使这个子段中所有数字的和最大，并输出这个最大和。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数，表示序列中的数字。

输出格式

输出一个整数，表示最大连续子段和。

输入输出样例

输入

9
-2 1 -3 4 -1 2 1 -5 4

输出

6

数据范围与提示

对于全部数据，$1 \le n \le 100000$，序列中每个整数的绝对值不超过 $10000$。

可以令 $dp[i]$ 表示“必须以第 $i$ 个数结尾”的最大连续子段和，则 $dp[i]=\max(a[i], dp[i-1]+a[i])$。答案是所有 $dp[i]$ 中的最大值。

来源

GESP 6 级动态规划训练。