C. Alternating Subsequence
C.交替子序列
time limit per test: 1 second
每次测试的时间限制：1秒
memory limit per test: 256 megabytes
每次测试的内存限制：256兆字节
input: standard input
输入：标准输入
output: standard output
产出：标准产出
Recall that the sequence b is a a subsequence of the sequence a if b can be derived from a by removing zero or more elements without
回想一下，序列b是序列a的子序列，如果b可以通过移除零或多个元素而不从a派生。
changing the order of the remaining elements. For example, ifa = 1, 2,1,3,1,2, 1]，then possible subsequences are: [1, 1,1,1], [3]
changing the order of the remaining elements. For example, ifa = 1, 2,1,3,1,2, 1]，then possible subsequences are: [1, 1,1,1], [3]
and [1,2, 1,3,1, 2, 1]. butnot [3, 2, 3] and[1,1,1,1,2].
和[1，2，1，3，1，2，1]。但不是[3，2，3]和[1，1，1，1，2]。
You are given a sequence a consisting of n positive and negative elements (there is no zeros in the sequence).
您将得到一个由n个正负元素组成的序列a(序列中没有零)。
Your task is to choose maximum by size (length) alternating subsequence of the given sequence (i.e. the sign of each next element is the
您的任务是按大小(长度)选择给定序列的交替子序列(即每个下一个元素的符号为
opposite from the sign of the current element, like positive-negative-positive and so on or negative-positive-negative and so on). Among all
与当前元素的符号相反，如正-负-正等或负-正-负-负等).在所有的人中
such subsequences, you have to choose one which has the maximum sum of elements.
这样的子序列，您必须选择一个元素的最大和。
In other words, if the maximum length of alternating subsequence is k then your task is to find the maximum sum of elements of some
换句话说，如果交替子序列的最大长度为k，那么您的任务就是找到一些元素的最大和。
alternating subsequence of length k.
长度k的交替子序列。
You have to answer t independent test cases.
您必须回答独立的测试用例。
Input
输入
The first line of the input contains one integert(1≤t≤10*)- - the number of test cases. Then t test cases follow.
The first line of the input contains one integert(1≤t≤10*)- - the number of test cases. Then t test cases follow.
The first line of the test case contains one integern(1≤n≤2. 10*)- the number of elements in a. The second line of the test case
测试用例的第一行包含一个整数(1≤n≤2.10*)–测试用例的第二行中的元素数。
contains n integers a1,a2…,an(-10’≤ai≤10’,ai≠0), where a; is the i-th element of a.
包含n个整数A1，a2.，an(-10‘≤ai≤10’，ai≠0)，其中a；是a的第一个元素。
It is guaranteed that the sum of n over all test cases does not exceed2. 10°(2n≤2. 105).
It is guaranteed that the sum of n over all test cases does not exceed2. 10°(2n≤2. 105).
Output
输出量
For each test case, print the answer一the maximum sum of the maximum by size (length) alternating subsequence of a.
对于每个测试用例，请打印答案(一)–按大小(长度)计算的最大和。
oj上消灭星星的变种
按正负分段每段取最大值
ll a[200007];
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
int cnt1=0,cnt2=0;
ll max1=-1e9;
for(int i=0;i<n;++i)
{
cin>>a[i];
if(a[i]<0)
cnt1++;
else
cnt2++;
max1=max(max1,a[i]);
}
if(cnt1==n||cnt2==n)
{
cout<<max1<<endl;
continue;
}
ll sum=0;
// int x=n-1;
for(int i=0;i<n;)
{
bool flag=0;
max1=-1e9;
while(a[i]>0&&i<n)
flag=1,max1=max(max1,a[i]),i++;
if(flag)
sum+=max1;
flag=0,max1=-1e9;
while(a[i]<0&&i<n)
flag=1,max1=max(max1,a[i]),i++;
if(flag)
sum+=max1;
}
cout<<sum<<endl;
}
return 0;
}
|