题目链接
题目
A subarray is a continuous part of array.
Yarik recently found an array a
of n
elements and became very interested in finding the maximum sum of a non empty subarray. However, Yarik doesn’t like consecutive integers with the same parity, so the subarray he chooses must have alternating parities for adjacent elements.
For example, [1,2,3]
is acceptable, but [1,2,4]
is not, as 2
and 4
are both even and adjacent.
You need to help Yarik by finding the maximum sum of such a subarray.
Input
The first line contains an integer t
(1≤t≤104)
— number of test cases. Each test case is described as follows.
The first line of each test case contains an integer n
(1≤n≤2⋅105)
— length of the array.
The second line of each test case contains n
integers a1,a2,…,an
(−103≤ai≤103)
— elements of the array.
It is guaranteed that the sum of n
for all test cases does not exceed 2⋅105
.
Output
For each test case, output a single integer — the answer to the problem.
Example
inputCopy
7
5
1 2 3 4 5
4
9 9 8 8
6
-1 4 -1 0 5 -4
4
-1 2 4 -3
1
-1000
3
101 -99 101
20
-10 5 -8 10 6 -10 7 9 -2 -6 7 2 -4 6 -1 7 -6 -7 4 1
outputCopy
15
17
8
4
-1000
101
10
题目大意
t
t
t 组测试数据
每组给一个整数
n
n
n 和
n
n
n 个整数（包含负数），问在这
n
n
n 个整数中，找和最大的连续子序列，要求是该子序列里的数是 奇偶交替的。
思路
这题我用的是dp的思路，定义一个状态数组f，对于
f
i
f_i
fi 是以
a
i
a_i
ai 开头的数列的最大值，
从后往前开始推，因为每个
f
i
f_i
fi都是最大的，
f
i
−
1
f_{i - 1}
fi−1 只用考虑在符合要求的前提下，是否要接上后面那串数列了。
f
i
=
m
a
x
(
f
i
,
f
i
+
f
i
+
1
)
f_i=max(f_{i}, f_i + f_{i + 1})
fi=max(fi,fi+fi+1)
代码
#include<bits/stdc++.h>
using namespace std;
const int N =1e6 + 10;
int a[N], f[N];
int main()
{
int T; cin >> T;
while (T -- )
{
int n; scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
f[i] = a[i]; //初始化状态
}
int ans = -0x3f3f3f3f;
for (int i = n - 1; i >= 1; i -- )
{
// 判断条件，是否符合一奇一偶的顺序
if (abs(a[i]) % 2 != abs(a[i + 1]) % 2)
{
f[i] = max(f[i], f[i] + f[i + 1]);
}
}
for (int i = 1; i <= n; i ++ )
{
ans = max(ans, f[i]);
}
printf("%d\n", ans);
}
return 0;
}
总结
好久没打CF，生疏了，第二题暴力，思路对了，但很多细节没写好，比如最大值答案用了0x3f3f3f3f，事实上在long long int 的情况下0x3f3f3f3f是不够大的，连续改大了两次才写对。
这题先写了一遍暴力，错了，然后才想的优化。
暴力版
#include<bits/stdc++.h>
using namespace std;
const int N =1e6 + 10;
int a[N], f[N];
int main()
{
int T; cin >> T;
while (T -- )
{
int n; scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
f[i] = a[i]
}
int ans = -0x3f3f3f3f;
for (int i = 1; i <= n; i ++ )
{
ans = max(ans, f[i]);
}
for (int i = 1; i <= n; i ++ )
{
int sum = a[i];
ans = max(sum, ans);
for (int j = i + 1; j <= n; j ++ )
{
// cout << a[j] << " " << a[j] % 2 << endl;
// cout << a[j - 1] << " " << a[j - 1] % 2 << endl;
if (abs(a[j] % 2) == abs(a[j - 1]) % 2)
{
// cout << 11111111 << endl;
break;
}
sum += a[j];
ans = max(ans, sum);
// cout << ans << endl;
}
}
printf("%d\n", ans);
}
return 0;
}
之前还写岔了一次，如果都是正数的话，可以像下面这么写
//正数版
#include<bits/stdc++.h>
using namespace std;
const int N =1e6 + 10;
int a[N];
int main()
{
int T; cin >> T;
while (T -- )
{
int n; cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
}
int ans = -0x3f3f3f3f;
int sum = a[1];
ans = max(sum, ans);
for (int i = 2; i <= n; i ++ )
{
if (a[i] % 2 == a[i - 1] % 2)
{
ans = max(sum, ans);
sum = a[i];
}
else
{
sum += a[i];
}
ans = max(sum, ans);
}
ans = max(sum, ans);
cout << " " << ans << endl;
}
return 0;
}
