题目内容

有一个包含 $n$ 个整数的序列 $e_1,e_2,\dots,e_n$，表示 $n$ 个能量核心的初始能量。你可以进行任意多次操作，每次操作选择两个不同的位置 $i,j$（$1 \le i, j \le n$，$i eq j$），将 $e_i$ 修改为 $e_i + e_j$，并将 $e_j$ 修改为 $0$。

请计算经过若干次操作后，序列全部前缀最大值之和的最大可能值，即 $\sum_{i=1}^{n} \max(e_1, e_2, \dots, e_i)$ 的最大值。

数据范围：测试数据组数 $T$ 不超过 $10^4$，每组数据中 $n$ 不超过 $2 \times 10^5$，所有测试数据的 $n$ 总和也不超过 $2 \times 10^5$。每个能量的绝对值不超过 $n$。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试数据组数。接下来每组数据：第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示序列长度；第二行包含 $n$ 个整数 $e_1, e_2, \dots, e_n$（$-n \le e_i \le n$），表示初始能量。保证所有测试数据的 $n$ 总和不超过 $2 \times 10^5$。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写