题目描述
对于给定的整数序列 A={a1,a2,…,an},找出两个不重合连续子段,使得两子段中所有数字的和最大。我们如下定义函数 d(A):
d(A)=1≤s1≤t1<s2≤t2≤nmax{i=s1∑t1ai+j=s2∑t2aj}
我们的目标就是求出 d(A)。
输入格式
第一行是一个整数 T(T≤20),代表一共有多少组数据。
接下来是 T 组数据。
每组数据的第一行是一个整数,代表数据个数 n(2≤n≤100000),第二行是 n 个整数 a1,a2,…,an(∣ai∣≤10000)。
输出格式
对每组数据输出一行一个整数,即该组 d(A) 的值。
1
10
1 -1 2 2 3 -3 4 -4 5 -5
13
提示
就是求最大子段和问题,样例取 {2,2,3,−3,4} 和 {5},Baidu搜POJ 2479 Maximum sum,可获得大量经典最大子段和问题的题目解析,本题 O(n2) 算法超时,必须用 O(n) 算法。
来源
一本通在线评测 ybtbas-1305