题目描述:
子数组是数组的连续部分。
Yarik 最近发现了一个由 n 个元素组成的数组 a,于是他对寻找一个非空子数组的最大和非常感兴趣。然而,Yarik 不喜欢奇偶校验相同的连续整数,因此他选择的子数组必须有相邻元素的交替奇偶校验。
例如, [1, 2, 3] 可以接受,但 [1, 2, 4] 不行,因为 2和 4都是偶数且相邻。
你需要帮助 Yarik 找出这样一个子数组的最大和。
输入
第一行包含一个整数 t t t ( 1 ≤ t ≤ 1 0 4 ) (1 \le t \le 10^4) (1≤t≤104) - 测试用例数。每个测试用例的描述如下。
每个测试用例的第一行都包含一个整数 n n n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) (1 \le n \le 2 \cdot 10^5) (1≤n≤2⋅105) 。 ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) (1 \le n \le 2 \cdot 10^5) (1≤n≤2⋅105) - 数组的长度。
每个测试用例的第二行包含 n n n 个整数 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an ( − 1 0 3 ≤ a i ≤ 1 0 3 ) (-10^3 \le a_i \le 10^3) (−103≤ai≤103) 个元素。- 数组元素。
保证所有测试用例中 n n n 的总和不超过 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105 。
输出
对于每个测试用例,输出一个整数,即问题的答案。
思路分析:
看看能不能接上,如果可以接上,看看是接上好还是单独取好,如果不能接上直接另当前和为当前值即可
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#define int long long
using namespace std;
int w[300005];
bool check(int x,int y){
if(abs(x%2)==abs(y%2)) return true;
return false;
}
int n,t,sum,ans;
signed main()
{
cin>>t;
while(t--){
cin>>n;
sum=0;
ans=0;
for(int i=0;i<n;i++)
cin>>w[i];
sum=w[0];
ans=w[0];//先把第一个取了
for(int i=1;i<n;i++)
{
if(!check(w[i],w[i-1]))
sum=max(w[i],sum+w[i]);//看看是接上好还是直接取好
else
sum=w[i];
ans=max(sum,ans);
}
cout<<ans<<endl;
}
return 0;
}