最大连续子列和问题

题目描述

给定$\,K\,$个整数组成的序列$\,N_1,N_2, ...,N_K$，“连续子列”被定义为$\,N_i,N_{i+1}, ...,N_j$，其中$\,1\le i\le j\le K$。“最大连续子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列$\, -2, 11, -4,13, -5, -2$，其连续子列$\,11, -4, 13\,$有最大的和$\,20$。现要求你编写程序，计算给定整数序列的最大连续子列和。

输入格式

输入第$\,1\,$行给出正整数$\,K(\le10^5)$；

第$\,2\,$行给出$\,K\,$个整数，其间以空格分隔。

输出格式

在一行中输出最大连续子列和（保证在 int 范围内）。

如果序列中所有整数皆为负数，则输出$\,0$。

样例输入

6
-2 11 -4 13 -5 -2

样例输出

20