最大子串和
题号:NC235948
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给你一个数组 a ,包含 n 个整数,你需要在其中选择连续的几个(至少一个)数,使得它们的和最大,求出最大的和。


输入描述:

第一行输入一个正整数  ,表示数组 a 大小。

第二行输入 n 个整数  ,表示数组 a 。

输出描述:

输出一行,一个整数,表示最大字串和。
示例1

输入

复制
6
1 -2 5 2 -3 5

输出

复制
9

说明

你可以选择区间[3,6]的子串,他们的和为5+2-3+5=9
示例2

输入

复制
8
-3 2 -3 2 2 -1 3 -2

输出

复制
6