Description

输入一个非空整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子串。

求所有子串和的最大值。

如数组 1 3 -1 4 -2 的子串最大值为7，是1 3 -1 4组成的子串。

Input Format

第一行为数组大小n，1 ≤ n ≤ 100000

第二行为n个整数，保证所有数的和不超过INT_MAX。

Output Format

连续子数组的最大和

8
1 -2 3 10 -4 7 2 -5​

18​

Source

基础百练 数组与字符串