小苯的线性dp
题号:NC288923
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小苯有一个由 n 个正整数组成的数组 \{a_1, a_2, \dots, a_n\}。他打算执行一些“合并”操作来最大化数组的极差。一次“合并”操作描述为:
\hspace{23pt}\bullet\,选择一对相邻的数字,将这两个数字合并为它们相加的和。形式化的,选择一个下标 i\left(1 \leqq i<n\right),执行 a_i:=a_i+a_{i+1},随后删除 a_{i+1},其余元素按照原有顺序前后拼接。

\hspace{15pt}而小红觉得,如果允许小苯进行任意次“合并”操作的话有些太简单了,因此她限定小苯必须恰好执行“合并”操作 k 次,求最终数组能得到的最大极差。
\hspace{15pt}现在,请你独立地对 k\left(0 \leqq k < n\right) 的每一个 k,都求出上述问题的答案吧。

\hspace{15pt}数组的极差定义为数组中最大值和最小值的差。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 100\right) 代表数据组数,每组测试数据描述如下:
\hspace{15pt}第一行输入一个正整数 n\left(1< n\leqq 3 \times 10^3\right) 代表数组中的元素个数。
\hspace{15pt}第二行输入 n 个正整数 a_1, a_2, \dots, a_n\left(1\leqq a_i\leqq 10^9\right) 代表数组中的元素。

\hspace{15pt}除此之外,保证单个测试文件的 n 之和不超过 3 \times 10^3

输出描述:

\hspace{15pt}对于每一组测试数据,新起一行。输出 n 个整数 p_1, p_2, \dots, p_n,其中 p_i 表示恰好执行 i-1 次“合并”操作后,数组的最大极差。
示例1

输入

复制
2
4
2 1 3 4
5
4 2 1 3 4

输出

复制
3 6 6 0
3 6 6 6 0

说明

\hspace{15pt}对于第一组测试数据,以 k=2 为例:
\hspace{23pt}\bullet\,合并 a_2a_3,数组变为 \{2,4,4\}
\hspace{23pt}\bullet\,合并 a_2a_3,数组变为 \{2,8\}
\hspace{15pt}此时,数组的极差为 8-2=6,我们可以证明,这是全部合并方案中最大的。