A6493 | $Alice打扰别人睡觉$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

众所周知，人在睡觉的时候头上会出现一串"Z"字往上飘，而有些人的"Z"居然会往下飘。如果这些"Z"字被人摘走了那那个人就会被吵醒，Alice非常喜欢摘走这些人的"Z"字，然后把这些人吵醒。 大家都趴在一张桌子上睡觉，大家头上"Z"字的飘起高度可以形成一个一维向量数组 $\{ a_0, a_1, a_2, a_3... a_n \}$ ，Alice可以一次性吵醒一个区间 $[ l , r ] (0≤l≤r≤n)$ 内的所有人，这些人对应的向量会被移除这个数组，Alice是一个超级大坏蛋，所以她可以无限次进行这种恶心人的行为，也可以一次都不进行。 Alice怎么这么坏啊！你要写一段程序得到Alice吵醒哪些人之后能让数组留下的向量和的模最大。 (一维向量是‌只有一个分量的向量‌，通常用单个数值表示，其方向由数值的正负号决定（正数表示一个方向，负数表示相反方向），大小（模）为该数值的绝对值。‌‌)

一共 $2n+1$ 行，第 $1$ 行表示有 $n$ ( $2\leqn\leq500$ )组测试用例。 接下来每 $2$ 行是一个测试用例 每个测试的第 $1$ 行有 $1$ 个数 $size$ ( $1\leqsize\leq500$ )，$size$ 表示这个桌子上有几个人在睡觉。 第 $2$ 行有 $size$ 个数，表示这些人的"Z"会飘多高的一维向量数组。( $-1\cdot10^5\leq一维向量\leq1\cdot10^5$ )

对于每组测试数据，新起一行，共 $n$ 行。 每一行输出一个整数代表Alice这么做后的最大的向量和的模。

输入 #1

2
5
1 2 -2 -3 4
7
2 5 -5 1 1 1 -6

输出 #1

7
11

C++ 编辑器

输入

输出