#1399. 序列分段
序列分段
题目描述
给定长度为 的序列 ,要求将 分割成恰好 段,每一段内的所有数字都求和,得到一个长度为 的序列 。
接着,最大化以下式子的和:
即:。
更通俗的:
请最大化:“第一段的和乘 ,加上第二段的和乘 ,一直加到第 段的和乘 ”。
现在,请你对每一个 ,都求出并回答上述式子的最大值吧。
输入格式
本题有多组测试数据。
输入的第一行包含一个正整数 ,表示数据组数。
接下来包含 组数据,每组数据的格式如下:
第一行一个正整数 ,表示序列 的长度。
第二行 个整数 ,表示序列 。
输出格式
对于每组测试数据:
在单独的一行输出由空格分隔的 个整数,其中第 个整数表示:把数组分为 段时,上述式子的最大值。
样例
2
6
1 3 -4 5 -1 -2
1
100
2 4 5 3 1 -2
100
题目来源:洛谷 U552155