给定一个长度为 $ 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 $