题目分析

给定一个数组，可以进行任意次操作：每次选择两个不同的下标 i 和 j，将 a[i] 修改为 a[i] + a[j]，并将 a[j] 修改为 0。操作的目标是最大化数组的所有前缀最大值之和。

解题思路

1. 观察操作的影响：每次操作实际上是将 a[j] 的值累加到 a[i] 上，并将 a[j] 置零。这意味着我们可以将所有正数集中到一个位置，而其他位置为零。
2. 最大化前缀和：如果所有正数都集中到一个位置（比如第一个位置），那么所有前缀的最大值都会是这个正数的和。此时，前缀最大值之和为 sum_of_positives * n。
3. 特殊情况处理：
   • 如果数组长度为 1，直接返回该元素的值。
   • 如果数组长度为 2，考虑将一个数加到另一个数上，无论加到哪个位置，非负结果最大。若合并后的数为负，则最大只能取0，否则前缀最大值和为2倍该数。特殊情况下如果第一个为正，第二个为负，则计算两次第一个数。
   • 如果数组长度大于等于 3，将所有正数集中到一个位置是最优的，因为这样可以让所有前缀的最大值都是这个正数的和。

代码实现

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        int sum = 0;
        if (n == 1) {
            cout << a[0] << endl;
            continue;
        }
        if (n >= 3) {
            for (int i = 0; i < n; i++) {
                if (a[i] > 0) sum += a[i];
            }
            cout << sum * n << endl;
            continue;
        }
        if (a[0] < 0) {
            int temp = a[0] + a[1];
            temp = max(0LL, temp);
            cout << temp * 2 << endl;
        }
        else{
            if(a[1] >= 0)cout << (a[0]+a[1]) * 2 << endl;
            else{
                cout << (a[0] * 2) << endl;
            }
        } 
    }
    return 0;
}

Python 代码

import sys

def solve():
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    for _ in range(T):
        n = int(input[ptr])
        ptr += 1
        a = list(map(int, input[ptr:ptr + n]))
        ptr += n
        sum_pos = 0
        if n == 1:
            print(a[0])
            continue
        if n >= 3:
            for num in a:
                if num > 0:
                    sum_pos += num
            print(sum_pos * n)
            continue
        # n == 2
        if a[0] < 0:
            temp = a[0] + a[1]
            temp = max(0, temp)
            print(temp * n)
        else:
            if a[1] >= 0:
                print((a[0]+a[1]) * 2)
            else:
                print(a[0] * 2)

solve()

Java 代码

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[] a = new int[n];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }
            long sum = 0;
            if (n == 1) {
                System.out.println(a[0]);
                continue;
            }
            if (n >= 3) {
                for (int num : a) {
                    if (num > 0) {
                        sum += num;
                    }
                }
                System.out.println(sum * n);
                continue;
            }
            // n == 2
            if (a[0] < 0) {
                long temp = a[0] + a[1];
                temp = Math.max(0, temp);
                System.out.println(temp * 2);
            } else {
                if(a[1] >= 0){
                    System.out.println((long) (a[0]+a[1]) * 2);
                }
                else{
                    System.out.println((long) a[0] * 2);
                }
            }
        }
    }
}

题目内容

给定一个由 $n$ 个整数构成的数组 {$a_1,a_2,...,a_n$} ，你可以进行以下操作任意次：

• 选取两个不同的下标 $i,j(1 ≦ i,j≦ n,i≠j)$ ，同时将 $a_i$ 修改为 $a_i+a_j$ ，并将 $a_j$ 修改为 $0$ 。

请你输出在若干次操作后，数组的全部 $n$ 个前缀最大值之和。换句话说，计算下式的答案：

$\sum^n_{i=1}max(a_1,a_2,...,a_i)$

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤ T≤ 10^4)$ 代表数据组数。此后对于每组测试数据：

第一行输入一个整数 $n(1≦n≦2×10^5)$ ，表示数组的长度；

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(-n ≦a_i≦ n)$ ，表示数组的元素。

此外，保证所有测试数据中 $n$ 的总和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，输出一个整数，表示所求的最大值。

样例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$ 。