题目描述

给定一个长度为 $n$ 的非零整数数组 $a$。初始时你拥有 0 枚硬币。你需要重复执行以下操作直到数组 $a$ 变为空：

1. 设当前数组 $a$ 的大小为 $m$。
2. 选择一个索引 $i$（$1 \le i \le m$）。
3. 获得 $|a_i|$ 枚硬币（$a_i$ 的绝对值）。
4. 执行移除操作：
   • 如果 $a_i < 0$（负数），则将数组 $a$ 替换为其前缀 $[a_1, a_2, \ldots, a_{i-1}]$ （即删除从 $a_i$ 开始的后缀）。
   • 如果 $a_i > 0$（正数），则将数组 $a$ 替换为其后缀 $[a_{i+1}, a_{i+2}, \ldots, a_m]$ （即删除以 $a_i$ 结尾的前缀）。

目标是计算通过一系列操作能获得的 最大 硬币数量。

样例

输入:
3
6
3 1 4 -1 -5 -9
6
-10 -3 -17 1 19 20
1
1

输出:
23
40
1

样例 1 解释

一种获得 23 硬币的操作序列：
- $a = [3, 1, 4, -1, -5, \text{-9}] \xrightarrow{i = 6} a = [3, 1, 4, -1, -5]$，获得 9 硬币。
- $a = [\text{3}, 1, 4, -1, -5] \xrightarrow{i = 1} a = [1, 4, -1, -5]$，获得 3 硬币。
- $a = [\text{1}, 4, -1, -5] \xrightarrow{i = 1} a = [4, -1, -5]$，获得 1 硬币。
- $a = [4, -1, \text{-5}] \xrightarrow{i = 3} a = [4, -1]$，获得 5 硬币。
- $a = [4, \text{-1}] \xrightarrow{i = 2} a = [4]$，获得 1 硬币。
- $a = [\text{4}] \xrightarrow{i = 1} a = []$，获得 4 硬币。
总计：9 + 3 + 1 + 5 + 1 + 4 = 23。

样例 2 解释

一种获得 40 硬币的操作序列：
- $a = [-10, -3, -17, \text{1}, 19, 20] \xrightarrow{i = 4} a = [19, 20]$，获得 1 硬币。
- $a = [\text{19}, 20] \xrightarrow{i = 1} a = [20]$，获得 19 硬币。
- $a = [\text{20}] \xrightarrow{i = 1} a = []$，获得 20 硬币。
总计：1 + 19 + 20 = 40。

算法 (贪心 / 前后缀和)

$O(N)$

思路分析

1. 理解操作:

   • 选择一个负数 $a_i$ 会移除包括 $a_i$ 在内的所有后缀元素，并获得 $|a_i| = -a_i$ 硬币。之后我们只能在 $a_i$ 之前的元素中继续操作。
   • 选择一个正数 $a_i$ 会移除包括 $a_i$ 在内的所有前缀元素，并获得 $|a_i| = a_i$ 硬币。之后我们只能在 $a_i$ 之后的元素中继续操作。

2. 操作序列的结构:
   考虑整个操作序列。假设我们选择了一个负数 $a_i < 0$，那么所有原始索引 $j \ge i$ 的元素（如果它们还存在的话）都会被移除。之后的所有操作都必须在原始索引 $j < i$ 的元素中进行。
   假设我们选择了一个正数 $a_i > 0$，那么所有原始索引 $j \le i$ 的元素（如果它们还存在的话）都会被移除。之后的所有操作都必须在原始索引 $j > i$ 的元素中进行。
   观察这两种操作的后果：

   • 选择负数 $a_i$ “锁定”了我们只能处理 $a_i$ 之前的部分。
   • 选择正数 $a_i$ “锁定”了我们只能处理 $a_i$ 之后的部分。
     这两种操作似乎是互斥的，从方向上看。如果我们选择了一个负数 $a_i$，之后就再也不能选择任何 $a_j$ (其中 $j \ge i$)，特别是不能选择任何正数 $a_k$ (其中 $k \ge i$)。反之，如果我们选择了一个正数 $a_i$，之后就再也不能选择任何 $a_j$ (其中 $j \le i$)，特别是不能选择任何负数 $a_k$ (其中 $k \le i$)。
     这强烈暗示，最优的操作序列必然存在一个“分割点” $k$（$0 \le k \le n$），使得所有被选择的负数 $a_i$ 都满足 $i \le k$，并且所有被选择的正数 $a_j$ 都满足 $j > k$。
     为什么这个分割策略是可行的并且包含了最优解？因为任何混合选择（比如先选 $a_i < 0$，再选 $a_j > 0$）必然要求 $j < i$；反之（先选 $a_j > 0$，再选 $a_i < 0$）必然要求 $i > j$。这两种情况都满足：所有选出的负数索引 $\le$ 某个值 $k$，所有选出的正数索引 $> k$。

3. 哪些元素会被选择？
   假设我们确定了一个分割点 $k$。我们的策略是：只考虑选择 $a_i$ 其中 $i \le k$ 且 $a_i < 0$，或者 $j > k$ 且 $a_j > 0$。
   在这种策略下，哪些元素必须被选择才能清空数组？

   • 考虑 $a_i$ 其中 $i \le k$ 且 $a_i < 0$。如果我们不选择它，它如何被移除？只能被某个 $a_p < 0$ (其中 $p \le i$) 移除，或者被某个 $a_q > 0$ (其中 $q \ge i$) 移除。但根据我们的策略，我们只会选择 $q > k$ 的正数。如果 $i \le k < q$，选择 $a_q > 0$ 会移除 $1..q$ 的前缀，这会移除 $a_i$。
   • 考虑 $a_j$ 其中 $j > k$ 且 $a_j > 0$。如果我们不选择它，它如何被移除？只能被某个 $a_p > 0$ (其中 $p \ge j$) 移除，或者被某个 $a_q < 0$ (其中 $q \le j$) 移除。但根据我们的策略，我们只会选择 $q \le k$ 的负数。如果 $q \le k < j$，选择 $a_q < 0$ 会移除 $q..n$ 的后缀，这会移除 $a_j$。
     这个分析表明，只要我们选择所有满足 $i \le k$ 且 $a_i < 0$ 的 $a_i$ 和所有满足 $j > k$ 且 $a_j > 0$ 的 $a_j$，就一定能清空整个数组。为什么？因为最左边的负数选择会清除它和它右边的所有，最右边的正数选择会清除它和它左边的所有。最终数组会被清空。
     因此，对于一个给定的分割点 $k$，最优策略下被选择的元素集合恰好是：
     $$C_k = \{ i \mid 1 \le i \le k \text{ and } a_i < 0 \} \cup \{ j \mid k < j \le n \text{ and } a_j > 0 \}$$
     该策略的总得分为：
     $$S_k = \sum_{i \in C_k, a_i < 0} (-a_i) + \sum_{j \in C_k, a_j > 0} a_j$$
     我们可以将其改写为：
     $$S_k = \left( \sum_{i=1}^{k} \max(0, -a_i) \right) + \left( \sum_{j=k+1}^{n} \max(0, a_j) \right)$$

4. 计算最大得分:
   我们的目标是找到 $\max_{0 \le k \le n} S_k$。
   我们可以通过一次遍历来计算所有 $S_k$ 并找到最大值。

   • 设 pre[i] 为前缀中正数的和： pre[i] = ∑_{p=1}^{i} max(0, a_p)。
   • 设 suf[i] 为后缀中负数绝对值的和：suf[i] = ∑_{q=i}^{n} max(0, -a_q)。
   • 那么 $S_k = (\sum_{p=1}^{k} \max(0, -a_p)) + (\sum_{q=k+1}^{n} \max(0, a_q))$。
   • 这和我们之前的定义有点不同。让我们直接用代码中的变量来理解。

5. 代码逻辑分析:

   • suf = 0; for (...) if (a[i] < 0) suf += a[i];
     这行代码计算了所有负数的和（本身是负值或零）。所以 suf = $\sum_{i=0}^{n-1} \min(0, a_i)$ （使用 0-based 索引）。
   • ans = -suf;
ans 初始化为 -suf = $-\sum_{i=0}^{n-1} \min(0, a_i) = \sum_{i=0}^{n-1} \max(0, -a_i)$。
     这恰好是 $k=n$ 时（即分割点在数组末尾之后）的得分 $S_n$ (因为此时只选择所有负数)。
   • pre = 0; 初始化前缀正数和。
   • for (int i = 0; i < n; i++) { ... } 循环遍历数组，i 可以看作是当前正在考虑的分割点的位置（或者说，元素 $a_i$ 是最后一个可能属于“负数部分”的元素）。
     • if (a[i] < 0) { suf -= a[i]; }：如果 $a_i$ 是负数，它不再属于 $k=i$ 策略下的“后缀”（即 $j > k$ 的部分）。我们需要将它的绝对值 $(-a_i)$ 从总的负数绝对值和（即 -suf）中移除。代码通过 suf -= a[i] (即 suf = suf - a[i]) 来更新 suf。现在 suf 代表 $\sum_{j=i+1}^{n-1} \min(0, a_j)$。
     • else { pre += a[i]; }：如果 $a_i$ 是正数，它现在被包含在 $k=i$ 策略下的“前缀”（即 $j \le k$ 的部分）中。我们将 $a_i$ 加入前缀正数和 pre。现在 pre 代表 $\sum_{j=0}^{i} \max(0, a_j)$。
     • ans = max(ans, pre - suf);：计算当前分割点 $k=i$ 对应的得分。
       得分 $S_i = (\sum_{p=0}^{i} \max(0, -a_p)) + (\sum_{q=i+1}^{n-1} \max(0, a_q))$。
       代码计算的是 pre - suf。
       pre = $\sum_{p=0}^{i} \max(0, a_p)$。
       -suf = $-\sum_{q=i+1}^{n-1} \min(0, a_q) = \sum_{q=i+1}^{n-1} \max(0, -a_q)$。
       所以，pre - suf = $(\sum_{p=0}^{i} \max(0, a_p)) + (\sum_{q=i+1}^{n-1} \max(0, -a_q))$。
       等一下！ 这个计算结果和我们推导的 $S_k$ 不完全一样。
       $S_k = (\sum_{p=1}^{k} \max(0, -a_p)) + (\sum_{q=k+1}^{n} \max(0, a_q))$
       代码中 pre - suf = $(\sum_{p=0}^{i} \max(0, a_p)) + (\sum_{q=i+1}^{n-1} \max(0, -a_q))$ （使用 0-based）
       这对应的是：选择所有 $j \le i$ 中的正数，和所有 $q > i$ 中的负数。这正好是我们推导出的策略！分割点 $k$ 对应代码中的 i。
       pre 累加了 $j \le i$ 的正数 $a_j$。
       -suf 累加了 $q > i$ 的负数 $a_q$ 的绝对值。
       因此，pre - suf 就是对应分割点 $k=i$ 的总得分 $S_i$。
   • 循环结束后，ans 中存储了所有可能的分割点 $k=0, 1, \dots, n$ 对应的得分 $S_k$ 的最大值。

6. 结论: 该算法正确地计算了所有可能的分割策略的得分，并取其最大值，这就是问题的答案。

时间复杂度

• 计算初始的 suf：O(N)。
• 循环 N 次：内部操作是 O(1)。
• 总时间复杂度: O(N)。

空间复杂度

• 存储数组 a：O(N)。
• 几个变量：O(1)。
• 总空间复杂度: O(N)。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名，用于存储得分和中间和

// 解决单个测试用例的函数
void solve() {
    int n; // 数组长度
    cin >> n;

    vector<int> a(n); // 存储输入的数组 a
    for (int i = 0; i < n; i ++ ) {
        cin >> a[i];
    }

    // suf: 用于计算后缀部分的贡献，但其含义在循环中动态变化。
    // 初始时，suf 存储所有负数元素的 *和* (是一个负值或零)。
    i64 suf = 0;
    // pre: 用于计算前缀部分的贡献。
    i64 pre = 0; 
    // 计算初始的 suf (所有负数之和)
    for (int i = 0; i < n; i ++ ) {
        if (a[i] < 0) {
            suf += a[i];
        }
    }

    // ans: 存储找到的最大得分。
    // 初始化为 -suf，即所有负数绝对值之和。
    // 这对应于分割点 k = n 的情况 (只选择所有负数)。
    i64 ans = -suf; 

    // 遍历数组，i 代表当前的分割点位置 (分割点在 i 和 i+1 之间)
    // 考虑分割策略 k = i
    for (int i = 0; i < n; i ++ ) {
        // 处理元素 a[i]
        if (a[i] < 0) {
            // 如果 a[i] 是负数，它从 "后缀负数" 部分移到 "前缀负数" 部分。
            // 我们需要从 suf (负数之和) 中去掉 a[i]。
            // 相当于从 -suf (负数绝对值之和) 中去掉 -a[i]。
            suf -= a[i]; 
        } else {
            // 如果 a[i] 是正数，它从 "后缀正数" 部分移到 "前缀正数" 部分。
            // 我们把它加入前缀正数和 pre。
            pre += a[i];
        }

        // cerr << suf << " " << pre << "\n"; // 调试输出 (注释掉)

        // 计算当前分割点 k = i 对应的得分 S_i
        // S_i = (前缀正数和) + (后缀负数绝对值和)
        // pre = sum_{j=0}^{i} max(0, a[j])
        // -suf = sum_{j=i+1}^{n-1} max(0, -a[j])
        // score = pre + (-suf) = pre - suf
        ans = max(ans, pre - suf); // 更新最大得分
    }

    // 输出最终找到的最大得分
    cout << ans << "\n";
}

// 主函数
int main() {
    // 加速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; // 测试用例数量
    cin >> t;

    // 处理每个测试用例
    while (t -- ) {
        solve(); // 调用解决函数
    }    

    return 0; // 程序正常结束
}