#1763. 最大连续子序列和

最大连续子序列和

题目描述

张琪曼喜欢思考人生的意义,她发现每个人的一生不可能一帆风顺,或多或少总要经过 坎坷控折的考验。于是她将人的一生的每个关键时间点以数值表示,快乐值越高,分值越 高.痛苦值越高.分值越低甚至会成为负数。进一步研究,她又发现人的记忆总是会记住那 些快乐的时光,而淡忘痛苦的时光。于是她想统计出某个人连续最大的一段快乐时光总和是 多少。即给定K\red{K}个整数的序列(N1,N2,...,Nk)\red{(N_1,N_2, ... ,N_k)}其任意连续子序列可表示为(Ni,Ni+1,...,Nj\red{(N_i,N_i+1,...,N_j} ),\red{),}其中1\red{1≤}i\red{i≤}j\red{j≤}K,\red{K,}最大连续子序列是所有连续子序列中元素和最大的一个,例如,给 定序列(2,11,4,13,5,2),\red{(-2,11,-4,13,-5,-2),}其最大连续子序列为{11,4,13},\red{\{11,-4,13\},}最大和为20\red{20}。这即 是所谓的"最大连续子序列和"问题。

输入格式

输人n(n\red{n(n≤}100000)\red{100 000)}n\red{n}个整数。

输出格式

输出该序列中最大的连续子序列的和max\red{max}

样例

输入样例

5
1 2 -5 11 3

输出样例

14