A71407. 两段和
编程题
基础
知识点
题目描述
给定 n 个整数，请从 n 个整数中选择互不相交的 2 个连续的区间，使得这两个区间的所有数的和尽可能大。
请问这个最大和是多少？
输入格式
第一行一个正整数 n ，表示整数数量。
接下来一行有 n 个整数 a_i。
输出格式
输出最大和。
输入输出样例
输入 #1
7 2 -4 3 -1 2 -4 3
输出 #1
7
说明/提示
【样例解释】
选 [3,5] 和 [7,7] 两段的和是最大的。
【数据范围】
对于 30\% 的数据，n≤100；
对于另外 30\% 的数据，n≤1000；
对于 100\% 的数据，n≤10^5，−10^9≤a_i≤10^9。