#OJ2248. 书
书
书
Time Limit: 1 Sec Memory Limit: 128 MB
Description
wx有一本古老的魔法书,魔法书中有很多古老的咒语。每句咒语都蕴含着巨大的能量,现在wx必须利用咒语去打败恶龙,救出公主hjh。要想打败恶龙就必须要先知道咒语中的魔力是多少,据说一句咒语中的每段子咒语都会对咒语的魔力有贡献,但是断开的子咒语是没有作用的。现在给你一句咒语中每个咒文的魔力ai,请你帮wx计算一下这句咒语的最大魔力是多少。
Input
第一行输入一个T,表示有T组输入。接下来有T个输入。
每一组输入分为两行,第一行包含一个数字N (1 <= N <= 100000),表示咒语的长度。第二行输入咒语中的N个咒文的魔力值ai(0< ai <=1000000)
Output
对于每一个输入,在一行中输出这句咒语的最大魔力值。
Sample Input
3
5
1 2 3 4 5
3
2 3 3
4
2 3 3 2
Sample Output
105
27
52
HINT
第二组样例: 求所有连续子序列的和 :2 + 3 + 3 + (2 + 3) + (3 + 3) + (2 + 3 + 3) = 27 可以分别计算每个数字对于结果的贡献是多少(也就是每个数字能出现多少次,Hint君只能帮你到这里了~)