问题 21775 --子串和再续

21775: 子串和再续

时间限制: 3 Sec  内存限制: 64 MB
提交: 6  解决: 3
[提交][状态][讨论版][数据上传:][下载FPS3元][添加到购物车][下载测试数据3元][20kb]

题目描述

给你一个序列 S1, S2, S3, S4 ... Sx, ... Sn (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx ≤ 32767). 我们定义
sum(i, j) = Si + ... + Sj (1 ≤ i ≤ j ≤ n).现在给你一个 m(8>m>0&&m<n)你的任务是计算
sum(i1, j1) + sum(i2, j2) + sum(i3, j3) + ... + sum(im, jm) ;我们规定他是不相交的。
请输出m段最大和,比如:m = 2,n = 6 ,{-1 4 -2 3 -2 4} 它的结果是 9;

输入

输入 T,表示T组数据
第二行 分别是m,n;

输出

请输出m段最大和

样例输入

1
3 6
-1 4 -2 3 -2 4

样例输出

11

提示

来源

[提交][状态]