最大两段子段和

题目描述

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

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

最大化

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

输入格式

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

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