CF1343C Alternating Subsequence
题目描述
回忆一下，如果序列 \(b\) 是序列 \(a\) 的一个子序列，那么 \(b\) 可以通过从 \(a\) 中删除零个或多个元素（不改变剩余元素的顺序）得到。例如，如果 \(a=[1, 2, 1, 3, 1, 2, 1]\)，那么可能的子序列有：\([1, 1, 1, 1]\)，\([3]\) 和 \([1, 2, 1, 3, 1, 2, 1]\)，但不是 \([3, 2, 3]\) 和 \([1, 1, 1, 1, 2]\)。
现在给定一个由 \(n\) 个正数和负数组成的序列 \(a\)（序列中没有零）。
你的任务是从给定序列中选择一个长度最大的交错子序列（即每个相邻元素的符号都相反，如正-负-正-负或负-正-负-正等）。在所有这样的子序列中，你还需要选择一个元素和最大的子序列。
换句话说，若交错子序列的最大长度为 \(k\)，则你的任务是找到长度为 \(k\) 的交错子序列中元素和的最大值。
你需要回答 \(t\) 组独立的测试数据。
输入格式
输入的第一行包含一个整数 \(t\)（\(1 \le t \le 10^4\)），表示测试数据的组数。接下来有 \(t\) 组测试数据。
每组测试数据的第一行包含一个整数 \(n\)（\(1 \le n \le 2 \cdot 10^5\)），表示序列 \(a\) 的长度。第二行包含 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)（\(-10^9 \le a_i \le 10^9,\, a_i \ne 0\)），表示序列 \(a\) 的元素。
保证所有测试数据中 \(n\) 的总和不超过 \(2 \cdot 10^5\)（\(\sum n \le 2 \cdot 10^5\)）。
输出格式
对于每组测试数据，输出一个答案，即长度最大的交错子序列中元素和的最大值。
输入输出样例 #1
输入 #1
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
输出 #1
2
-1
6
-2999999997
说明/提示
在第一个样例中，其中一个可能的答案是 \([1, 2, \underline{3}, \underline{-1}, -2]\)。
在第二个样例中，其中一个可能的答案是 \([-1, -2, \underline{-1}, -3]\)。
在第三个样例中，其中一个可能的答案是 \([\underline{-2}, 8, 3, \underline{8}, \underline{-4}, -15, \underline{5}, \underline{-2}, -3, \underline{1}]\)。
在第四个样例中，其中一个可能的答案是 \([\underline{1}, \underline{-1000000000}, \underline{1}, \underline{-1000000000}, \underline{1}, \underline{-1000000000}]\)。
分块处理，找出同号块中的最大值，然后处理完所有的分块就找到了最大的和
#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T; cin >> T;while (T--) {int n; cin >> n;long long x; long long ans = 0;cin >> x;long long best = x; // 当前块最大值for (int i = 2; i <= n; ++i) {cin >> x;if ( (x > 0) == (best > 0) ) { // 同号，仍在同一块best = max(best, x);} else { // 换号，结算上一块ans += best;best = x; // 开新块}}ans += best; // 收尾：最后一块cout << ans << '\n';}return 0;
}