1003: 子数组3
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：1
题目描述
给出一个长度为$N$的数组，从该数组中移除一个长度最大为$N-1$的子数组，使得剩下的数组有元素值总和最大的子数组，找出这个最大值。
输入
第一行，$1$个整数，表示$N$
第二行，$N$个整数，表示数组的元素值${A_i}$
输出
一个整数，表示移除一个长度最大为$N-1$的子数组后，元素值总和最大的一个子数组的元素值总和
样例输入 复制
#1
5
10 -2 3 -10 5
#2
7
-3 2 -1 5 -7 9 -10
#3
5
1 -2 -3 4 -1样例输出 复制
#1
16
#2
15
#3
5提示
【样例解释】
对于样例1：
移除$[-10]$后，剩余数组为$[10,-2,3,5]$，子数组$[10,-2,3,5]$元素值总和最大，为$16$
对于样例2：
移除$[-7]$后，剩余数组为$[-3,2,-1,5,9,-10]$，子数组$[2,-1,5,9]$元素值总和最大，为$15$
对于样例3：
移除$[-2,-3]$后剩余数组为$[1,4,-1]$，子数组$[1,4]$元素值总和最大，为$5$
【数据范围】
对于20%的数据：
$-100 \leq {A_i} \leq 100$
$2 \leq N \leq 20$
对于100%的数据：
$-10^9 \leq {A_i} \leq 10^9$
$2 \leq N \leq 10^6$