最大双子段和(Maximum Two Subarray Sum)

给定一个长度为 $n$ 的整数序列，要求从中选出两个子段（序列中连续且非空的一段），使得这两个子段中的整数的总和最大，并输出所求的两个子段中的整数的总和。每个子段的最小长度为 $1$ ，并且两个子段之间至少间隔一个数。

第一行是一个整数，表示 $n$ 。

第二行是 $n$ 个整数，表示整数序列。

一个整数，表示所求的两个子段中的整数的总和。

5
83 223 -13 1331 -935

3
83 223 -13

对于 $30\%$ 的数据，有 $N\le 100$ 。

对于 $60\%$ 的数据，有 $N\le 10^4$ 。

对于 $100\%$ 的数据，有 $N\le 10^6$ 。

数据保证运算过程中的所有数值均在 64 位有符号整型的表示范围内。

本题涉及的知识点从属于 CSP-J，难度（CF Rating）：1300。

Subtask	分值	测试点编号	说明
0	10	1~2	样例及最小边界测试
1	20	3~8	$3 \le n \le 100$ ，$
2	15	9~11	Hack 数据：全负数序列（答案不能误取 $0$ ）、 $n = 3$ 必须强制隔开中间元素
3	30	12~20	$1000 \le n \le 2 \times 10^5$ ，$
4	25	21~25	$5 \times 10^5 \le n \le 10^6$ 极限规模线性 DP 测试

出处：原题链接

#P2642. 最大双子段和(Maximum Two Subarray Sum)