题目描述

【背景】

       加速度计是测量加速度的仪表。加速度测量是工程技术提出的重要课题。 
       要知道各瞬时飞机、火箭和舰艇所在的空间位置，可通过惯性导航系统连续地测出其加速度，然后经过积分运算得到速度分量，再次积分得到一个方向的位置坐标信号，而三个坐标方向的仪器测量结果就综合出运动曲线并给出每瞬时航行器所在的空间位置。 
       再如某些控制系统中，常需要加速度信号作为产生控制作用所需的信息的一部分，这里也出现连续地测量加速度的问题。能连续地给出加速度信号的装置称为加速度传感器。 
       但是，加速度计并非每一次传回的数值都是准确且稳定的，我们需要进行“滤波”，即人为地过滤掉显然错误的数据。

【题目】

        给定一个长度为$n$的数组，即加速度计周期性发出的连续的$n$组数据。已知加速度计发出的每一个数据都可正可负。你的任务是：在这组数据中找出一个子列（即从长度为$n$的数组中任意截取连续的一段作为新的数组），使得这个子列的和最大。

输入格式

       第一行是一个整数$n$表示加速度计发出的数据长度 
       第二行是$n$个用空格分开的整数，表示加速度计的数据

输出格式

       一行一个整数，表示最大子列和

5

1 -1 1 -1 1

1

6

-1 3 -2 4 5 -6

10

提示

       对于50%的数据，$1$<=$n$<=$500$
       对于70%的数据，$1$<=$n$<=$5000$
       对于100%的数据，$1$<=$n$<=$500000$、$1$<=$|a[i]|$<=$100 $

       对于第一个样例： 
       最大子列和为 1 或 1+(-1)+1=1 或 1+(-1)+1+(-1)+1=1 
       对于第二个样例： 
       最大子列和为 3+(-2)+4+5=10 
       没有其他的方案能产生更大的子列和