【MX-S2-T2】排
题目描述
有 $n$ 个整数 $a_1,a_2,\ldots,a_n$。$f_0=0,f_i= \left\{
\begin{aligned}
& f_{i-1} & \ f_{i-1}\times a_i>0, \\
& f_{i-1}+a_i & \ f_{i-1}\times a_i\le 0.\\
\end{aligned}
\right.
$
重排 $a$ 使得得到的 $f_n$ 最大。
输入输出格式
输入格式
第一行一个整数 $n$。
第二行 $n$ 个整数 $a_1,\dots,a_n$。
输出格式
一行一个整数，表示答案。
输入输出样例
输入样例 #1
5
7 5 -4 -6 3输出样例 #1
6输入样例 #2
10
573 -1339 899 939 -26 1430 1324 -1150 1640 -45 输出样例 #2
1625说明
**【样例解释 \#1】**
考虑重排为 $-6,-4,5,7,3$，最终的 $f_n$ 为 $6$，可以证明不存在更优的方案。
**【数据范围】**
**本题采用捆绑测试。**
- Subtask 0（6 pts）：$n\le10$。
- Subtask 1（14 pts）：$n\le 20$，$|a_i|\le10$。
- Subtask 2（8 pts）：$a$ 中全为正数或全为负数。
- Subtask 3（19 pts）：$a$ 中有且只有一个正数（注意 $a$ 中可以有 $0$）。
- Subtask 4（29 pts）：$n \le 200$，$|a_i|\le 200$。
- Subtask 5（24 pts）：无特殊限制。
对于所有测试数据，$1 \le n \le 2000$，$|a_i|\le 2000$。