跳至正文
题库3980
#3980

1305. Maximum sum

查看题目操作

1305. Maximum sum

题目描述

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

d(A)=max⁡1≤s1≤t1<s2≤t2≤n{∑i=s1t1ai+∑j=s2t2aj}d(A) = \max_{1 \le s_1 \le t_1 < s_2 \le t_2 \le n}\left\{\sum_{i=s_1}^{t_1}a_i+\sum_{j=s_2}^{t_2}a_j\right\}

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

输入格式

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

接下来是 TT 组数据。

每组数据的第一行是一个整数,代表数据个数 n(2≤n≤100000)n(2 \le n \le 100000),第二行是 nn 个整数 a1,a2,…,an(∣ai∣≤10000)a_1, a_2, \ldots, a_n(|a_i| \le 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) 算法。

来源

一本通在线评测 ybtbas-1305