P3382.第1题-大，大大，大大大
题目内容
给定一个由 n 个整数构成的数组 {a1,a2,...,an} ，你可以进行以下操作任意次：
- 选取两个不同的下标 i,j(1≦i,j≦n,i=j) ，同时将 ai 修改为 ai+aj ，并将 aj 修改为 0 。
请你输出在若干次操作后，数组的全部 n 个前缀最大值之和。换句话说，计算下式的答案：
∑i=1nmax(a1,a2,...,ai)
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤104) 代表数据组数。此后对于每组测试数据：
第一行输入一个整数 n(1≦n≦2×105) ，表示数组的长度；
第二行输入 n 个整数 a1,a2,...,an(−n≦ai≦n) ，表示数组的元素。
此外，保证所有测试数据中 n 的总和不超过 2×105 。
输出描述
对于每组测试数据，输出一个整数，表示所求的最大值。
样例1
输入
2
3
3 2 -1
1
-1
输出
15
-1
说明
对于第一组数据，其中一种最优选择方案为 i=1,j=2，操作后数组变为 {5,0,−1}，表达式之和即为 5+max(5,0)+max(5,0,−1)=15 。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
