D. Maximum Sum on Even Positions(最大连续字段和)

Problem - 1373D - Codeforces

题意:

 

给你一个由n个整数组成的数组a。数组的索引从零开始（即第一个元素是a0，第二个是a1，以此类推）。

你最多可以扭转这个数组的一个子数组（连续子段）。回顾一下，a的边框为l和r的子数组是a[l;r]=al,al+1,...,ar。

你的任务是反转这样一个子数组，使所得数组的偶数位置上的元素之和达到最大（即整数k=⌊n-1/2⌋的元素之和应该是最大的）。

你必须回答t个独立的测试案例。

输入
输入的第一行包含一个整数t（1≤t≤2⋅104）--测试案例的数量。然后是t个测试用例。

测试用例的第一行包含一个整数n（1≤n≤2⋅105）--a的长度。测试用例的第二行包含n个整数a0,a1,...,an-1（1≤ai≤109），其中ai是a的第i个元素。

保证n的总和不超过2⋅105（∑n≤2⋅105）。

输出

例子
输入复制
4
8
1 7 3 4 7 6 2 9
5
1 2 1 2 1
10
7 8 4 5 7 6 8 9 7 3
4
3 1 2 1

输出拷贝
26
5
37
5

题解:

如果反转的子数组长度是奇数,对答案无影响,所以我们应该只考虑,偶数的情况,首先我们把偶数位的数相加为最小可能情况

其次子数组可能以奇数位,或偶数位开头,所以也要分情况

如果反转,那么对于答案的贡献,相当于奇数位-偶数位的数值

因为偶数与奇数位的值都会交换位置,我们已经统计了偶数位的值,所以如果相减的结果大于0,就可以看作是对结果的贡献,就继续遍历加上

当然,也会有小于0的情况,说明从之前某一位开头的,到这的子数组是对答案无贡献的,就把遍历到此的贡献变为0,代表从现在开始的子数组

途中找贡献的最大值即可

#include<iostream>
#include<algorithm>
using namespace std;
long long a[200050];
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		long long s1 = 0,s2 = 0,ma = 0;
		int n;
		cin >> n;
		long long ans = 0;
		for(int i =1;i <= n;i ++)/
		{
			cin >> a[i];
			if(i&1)//由于我首位下标从1开始,所以奇数位相加
			{
				ans += a[i];
			}
		}
		for(int i = 2;i <= n;i +=2)
		{
			s1 = max((long long)0,a[i] - a[i-1]+s1);
			ma = max(ma,s1);
		}
		for(int i = 3;i <= n;i +=2)
		{
			s2 = max((long long)0,a[i-1]-a[i]+s2);
			ma = max(ma,s2);
		}
		cout<<ans+ma<<'\n';
	}
}