该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定长度为n的整数序列，a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大.或者求出最大的这个和.例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4].

Input Format

第一行输入n，表示n个整数

第二行输入n个整数，整数之间用空格隔开

Output Format

输出最大子段和

5
11 -4 13 -5 2

20

Source