最大子段和（分治）

题目描述

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

本题要求使用分治法求解。

输入

• 第一行包含一个整数 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 。

数据范围与约定

• 对于 30% 的数据， n \le 100 。
• 对于 100% 的数据， n \le 10^6 。
• 序列元素绝对值不超过 10^9 。