题解：CF1899C Yarik and Array

原题链接

• 洛谷 CF1899C Yarik and Array

解题思路

对于第 $2\sim n$ 个元素，分类讨论：

• 若能与前面的元素接上，取接或不接的最大值。
• 否则，只能选择不接。

实时更新最大值即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=200005;
int a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		int sum=a[1],ans=a[1];
		for(int i=2;i<=n;i++)
		{
			if(a[i]-a[i-1]&1)
			{
				sum=max(sum+a[i],a[i]);
			}
			else
			{
				sum=a[i];
			}
			ans=max(ans,sum);
		}
		cout<<ans<<'\n';
	}
	return 0;
}