#683. [ybt]1305

[ybt]1305

【题目描述】

对于给定的整数序列A={a1,a2,...,an}A=\{a_1, a_2,..., a_n\},找出两个不重合连续子段,使得两子段中所有数字的和最大。我们如下定义函数 d(A)d(A)

$$d(A) = \begin{matrix}max\\1≤s_1≤t_1≤s_2≤t_2≤n \end{matrix} \left\{ \sum_{i=s_1}^{t_1}a_i+\sum_{j=s_2}^{t_2}a_j \right\} $$

我们的目标就是求出d(A)d(A)

【输入】

第一行是一个整数T(30)T(≤30),代表一共有多少组数据。

接下来是TT组数据。

每组数据的第一行是一个整数,代表数据个数据n(2n50000)n(2≤n≤50000) ,第二行是nn个整数a1,a2,...,an(ai10000)a_1, a_2, ..., a_n(|a_i| ≤ 10000)

【输出】

输出一个整数,就是d(A)d(A)的值。

【输入样例】

1
10
1 -1 2 2 3 -3 4 -4 5 -5

【输出样例】

13

【提示】

就是求最大子段和问题,样列取2,2,3,3,4{2,2,3,-3,4}5{5},Baidu搜POJ 2479 Maximum sum,可获得大量经典最大子段和问题的题目解析,本题O(n2)O(n^2)算法超时,必须用O(n)O(n)算法。

【来源】

一本通在线评测