#1033. 最大和子序列

最大和子序列

题目描述

设数组a\red{a}是有n\red{n}个元素的整数数组,从中找出最大和子序列。

最大和子序列:数组中连续元素(子序列)相加和的最大值。

数组:-6 2 4 -7 5 3 2 -1 6 -9 10 -2

最大和子序列为16\red{16},最大子序列为:5 3 2 -1 6 -9 10

输入格式

第一行一个整数n\red{n}n<=1000\red{n<=1000}

第二行,n\red{n}个绝对值不大于10000\red{10000}的整数。

输出格式

一个整数,子序列和中最大值。

样例

输入数据

12
-6 2 4 -7 5 3 2 -1 6 -9 10 -2

输出数据

16