题目背景

在美丽的珊瑚海中，有一条聪明的小鱼$FISH$。它要穿越一片神秘的海域，海域中有$n$个珊瑚礁排成一排，每个珊瑚礁上都有一定数量的海藻（能量值）。小鱼可以从任意珊瑚礁出发，但每次只能跳到相邻的珊瑚礁上吃海藻。为了完成这次冒险，小鱼需要找到一条路径，使得吃掉的海藻总能量最大！

题目描述

给定一个整数数组，表示每个珊瑚礁上的海藻能量值（可能为负数，表示有毒海藻）。请找出一个连续子数组，使其和最大，并输出这个最大和。

输入数据

共有两行。 第一行一个整数$n$，表示珊瑚礁数量 第二行$n$个整数，表示每个珊瑚礁的海藻能量值

输出数据

一个整数，表示最大能量和

样例

8
2 -1 3 -4 5 -2 1 3

7

样例解析

从索引$4$开始：$5 = 5$ 继续：$5-2 = 3$ 继续：$5-2+1 = 4$ 继续：$5-2+1+3 = 7$

限制

限制在$1s$, $256MiB$。

数据保证

保证$1≤n≤10^{7}$,$-1000≤能量值≤1000$