最大子段和

题目描述

给定一个长度为 n 的整数序列 a_1, a_2, \dots, a_n ，请找出一个连续的非空子段，使得该子段内所有整数之和最大。输出这个最大和。

例如，序列 3 1 -6 1 7 5 -2 5 -100 10 的最大子段和为 16（取子段 1 7 5 -2 5）。

输入

• 第一行包含一个整数 n （ 1 \le n \le 10^6 ），表示序列的长度。
• 第二行包含 n 个整数 a_1, a_2, \dots, a_n ,（ |a_i| \le 10^9 ），表示序列中的元素。

输出

输出一个整数，表示最大子段和。

样例

提示

样例说明

最大子段为 1 7 5 -2 5，其和为 1+7+5-2+5 = 16 。

数据范围与约定

• 1 \le n \le 10^6
• |a_i| \le 10^9

来源

动规专题