题目描述

难度分:$1200$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9$且 $a[i] \neq 0)$。

选一个$a$的子序列，要求：

1. 子序列是交替的（相邻元素一正一负）。
2. 在满足$1$的前提下，子序列尽量长。
3. 在满足$2$的前提下，子序列元素和尽量大。

输出元素和的最大值。

注：子序列不一定连续。

输入样例

4
5
1 2 3 -1 -2
4
-1 -2 -1 -3
10
-2 8 3 8 -4 -15 5 -2 -3 1
6
1 -1000000000 1 -1000000000 1 -1000000000

输出样例

2
-1
6
-2999999997

算法

贪心

由于所给的三个前提要按照优先级满足，因此对于任意符号相同的连续段，都要从中选择一个数作为子序列的一个元素，而为了让累加和最大，选择子数组中的最大值即可。

所以我们从$i=1$开始遍历数组，维护$i$开始的符号相同段最大值$mx$，以及符号$sign$（正数就是$1$，负数就是$-1$）。每当$a[i]$的符号和$sign$不相同时就更新$sign=-sign$，$mx=a[i]$，将$mx$累加到答案上，否则只更新$mx=max(mx,a[i])$。

注意最后一段没有变号点进行结算，因此遍历完整个数组后的$mx$也要加到答案上。

复杂度分析

时间复杂度

仅遍历了一遍数组$a$就求得了答案，时间复杂度为$O(n)$。

空间复杂度

除了输入的数组$a$，仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int T, n, a[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        int sign = a[1] > 0? 1: -1;
        int mx = a[1];
        long long ans = 0;
        for(int i = 2; i <= n; i++) {
            int sgn = a[i] > 0? 1: -1;
            if(sgn == sign) {
                mx = max(a[i], mx);
            }else {
                ans += mx;
                mx = a[i];
                sign = sgn;
            }
        }
        ans += mx;
        printf("%lld\n", ans);
    }
    return 0;
}