最大连续子串和

故事背景

一场游戏的得分记录可能有加分也有扣分。你想找到一段连续的得分区间，使得总得分尽可能高，用来分析“状态最好的那一段”。

题目描述

给定一个长度为 n 的整数数组 a，元素可以为正、为 0 或为负，求所有非空连续子数组中元素和的最大值。

输入格式

第一行包含一个整数 n。 第二行包含 n 个整数，表示数组 a 的元素。

输出格式

输出一个整数，表示最大连续子数组和。

输入输出样例 #1

输入 #1

9
-2 1 -3 4 -1 2 1 -5 4

输出 #1

6

样例解释 #1

选择子数组 [4, -1, 2, 1]，其和为 6，为所有连续子数组中最大。

说明/提示

• 数据范围：1 ≤ n ≤ 2×10^5，|a_i| ≤ 10^9。