题目链接
题目
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;
}