CF 1899C 学习笔记

C. Yarik and Array

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

A subarray is a continuous part of array.

Yarik recently found an array 𝑎� of 𝑛� 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][1,2,3] is acceptable, but [1,2,4][1,2,4] is not, as 22 and 44 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 𝑡� (1≤𝑡≤104)(1≤�≤104) — number of test cases. Each test case is described as follows.

The first line of each test case contains an integer 𝑛� (1≤𝑛≤2⋅105)(1≤�≤2⋅105) — length of the array.

The second line of each test case contains 𝑛� integers 𝑎1,𝑎2,…,𝑎𝑛�1,�2,…,�� (−103≤𝑎𝑖≤103)(−103≤��≤103) — elements of the array.

It is guaranteed that the sum of 𝑛� for all test cases does not exceed 2⋅1052⋅105.

Output

For each test case, output a single integer — the answer to the problem.

Example

input

Copy

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

output

Copy

15
17
8
4
-1000
101
10

#include
using namespace std;
 
const int N=2e5+10;
int a[N],f[N];
 
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			f[i]=a[i];
		}
		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]);
			}
		}
		int ans=-2e9;
		for(int i=1;i<=n;i++)
		{
			ans=max(ans,f[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}

赛时没有写出来，题目读懂了，但是写不出，该题属于一道动态规划的题目。

题目的意思是：输入一个数组，求这个数组的一段连续序列，要求这段连续序列尽可能长，总和尽可能大，相邻两个元素奇偶性不同 。

a数组用来存储数组元素，f数组用来存储某一段连续序列的和。输入所有数组元素的同时，初始化f数组，使得f数组最开始和a数组相同

从最后一个元素开始处理，建立状态转移方程，进行奇偶性校验，如果相邻元素奇偶性不同，更新f数组，决定是否要把后面一段元素加上，从后面处理到前面，处理前面的元素的时候，后面的元素已经完成了预处理，所以可以解决这个问题

最后面遍历f数组，找到f数组里面的最大值，即我们寻找的答案，输出即可

参考题解：

1.题解1

2.cf官方题解