题目背景

Special for beginners, ^_^

题目描述

给定一个长度为 𝑛 的整数数组 𝑎。

请找出一个连续子数组，使其元素之和最大，并输出这个最大值。

要求使用 递归（分治）方法解决。

输入格式

第一行一个整数 𝑛 1 ≤ n ≤ 2×10^5 第二行 n 个整数 -10^9 ≤ a[i] ≤ 10^9

输出格式

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

样例

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

6

样例解释

最大连续子数组为：

4 -1 2 1

它们的和为：

4 + (-1) + 2 + 1 = 6

因此最大子段和为 6。