最大两段子段和

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$，请从中选择恰好两段互不重叠的非空连续子段，使两段内所有数字的总和最大。

也就是说，选择下标 $l_1,r_1,l_2,r_2$，满足

$$1\le l_1\le r_1<l_2\le r_2\le n,$$

最大化

$$\sum_{i=l_1}^{r_1}a_i+\sum_{i=l_2}^{r_2}a_i.$$

两段可以相邻，中间不要求留出未选择的数字。序列首尾不相连。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

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

样例 1

5
2 -5 4 3 -1

9

选择子段 $[1,1]$ 和 $[3,4]$，总和为 $2+4+3=9$。

样例 2

4
-8 -2 -5 -4

-6

选择子段 $[2,2]$ 和 $[4,4]$，总和为 $-2-4=-6$。即使所有数字均为负数，也必须选择两段。

数据范围与评分

所有测试数据满足 $2\le n\le200000$，$-10^9\le a_i\le10^9$。

测试组	分值	附加限制
1	20 分	$n\le200$
2	30 分	$n\le2000$
3	50 分	无

每组内全部测试点通过才能获得该组分数。答案可能超出 32 位整数范围，请使用 64 位整数。