Description

题目描述

给定n个整数a1,a2,⋯,an​构成一个序列，请为这个序列寻找一个子串，使数字之和达到最大。

子串是原序列中连续且保持顺序的一段数字，空串或序列全体都算原序列的子串。

Input Format

第一行：单个整数n。

第二行：n个整数a1,a2,…,an​。

Output Format

单个整数：表示子串的最大和。

5
1 2 -10 2 3

5

Hint

对于30%的数据，1≤n≤200，

对于60%的数据，1≤n≤5000，

对于100%的数据，1≤n≤200,000。

−10000≤ai≤10000

Source