马格尼最大 (Easy Version)

题目描述

有多组数据，每组给出n个数字，对于这n个数字依次进行下述两种操作中的一种， 求n次操作后的最大值。

sum表示最大值 一、对于$a_i$，

​ sum= sum + $a_i$

​ 二、对于$a_i$ ​ ，sum= | sum + $a_i$|

输入格式

第一行一个数字t ( 1 $\leq t$ $\leq 10^4$ ) ，表示测试数据组数

紧接着一行数字n ($2 \leq n \leq 2 \cdot 10^5$) 表示当前数字个数

随后n行，$a_1$ ​ , $a_2$ ​ , $a_3$ ​ , $\ldots… , a_n$ ​ ( $-10^9 \leq a_i \leq 10^9$) ) 每组n个数字总和不超过$3 \cdot 10^5$

已知是dp，求助