1481: Maximum问题(2.6基本算法之动态规划)

1481:Maximum sum

总时间限制: 1000ms 内存限制: 65536kB
描述
对于一组 n 个整数：A={a1, a2,…, an}，我们定义一个函数 d(A) 如下：
t1 t2
d(A) = max{ ∑ai + ∑aj | 1 <= s1 <= t1 < s2 <= t2 <= n }
i=s1 j=s2

你的任务是计算 d(A)。
输入
输入由 T(<=30) 个测试用例组成。第一个输入行给出测试用例的数量 T。
每个测试用例包含两行。第一行是一个整数 n(2<=n<=50000)。第二行包含 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}，然后可以得到答案。

输入数据量较大，建议使用 scanf 进行读取。

    #include<iostream>
    #include<string.h>
    using namespace std;
    //http://noi.openjudge