因为只能转一个子数组，很显然转长度为奇数的子数组，对最大化答案是没有意义的（偶数位的数字之和不会变化）。因此只考虑转偶长度的子数组。
转动偶数长度的子数组，相当于子数组中奇位和偶位的数互换。
答案要求最大化偶数位之和（但是本题中从$0$开始计数。为了前缀和计算的便利，我在写代码时用$1$作为开头，于是目标变成了最大化奇数位之和）。在不转动时，初始的奇数位之和是固定的一个常数。设子数组是$a[L]..a[R]$，要最大化答案中奇数位之和，相当于最大化（被奇偶调换的）子数组中偶数位和与奇数位和的差，即最大化$a[L]..a[R]$中$sum_{偶位}-sum_{奇位}$。我们只需要找到这样一个$sum_{偶位}-sum_{奇位}$最大的子数组就行了。
开两个前缀和数组，$sum_{odd}$表示奇数位的前缀和，$sum_{even}$表示偶数位的前缀和，我们找最大的$(sum_{even}[j]-sum_{even}[i])-(sum_{odd}[j]-sum_{odd}[i])$，化简一下这个式子，化成$(sum_{even}[j]-sum_{odd}[j])-(sum_{even}[i]-sum_{odd}[i])$。
这个式子要求最大。我们就开个数组$d$，设$d[i]=sum_{even}[i]-sum_{odd}[i]$，在$i<j$的情况下，找最大的$d[j]-d[i]$。（这里的$sum_{odd}[i]$可以不用真实地存储下来，事实上我们可以直接在读入时对$d[i]$做个伪前缀和：$i$是奇数时$d[i]=d[i-1]-a[i]$，$i$是偶数时$d[i]=d[i-1]+a[i]$。）
找最大的$d[j]-d[i]$时，可以借助单调队列的想法，动态地求当前最小。需要注意到是子数组长度只能为偶数，因此需要对奇数位、偶数位分别做一次单调队列。
（需要注意的是，如果最大的$sum_{偶位}-sum_{奇位}$都小于$0$，那转动就是没有意义的，不用转动。）
#include <cstdio>
#include <vector>
using namespace std;
const int maxn=2e5;
int t,n;
long long d[maxn+5];
int main(){
scanf("%d",&t);
while (t--){
long long ans=0;
scanf("%d",&n);
d[0]=0;
long long x;
for (int i=1;i<=n;i++){
scanf("%lld",&x);
if (i%2)
ans+=x;
d[i]=d[i-1]+((i%2==0)?(x):(-x));
}
long long res=0;
vector<long long> que;
que.push_back(0);
for (int i=2;i<=n;i+=2){
while ((!que.empty())&&d[i]<d[que.back()]){
que.pop_back();
}
que.push_back(i);
if (d[i]-d[que.front()]>res)
res=d[i]-d[que.front()];
}
vector<long long> q;
for (int i=1;i<=n;i+=2){
while ((!q.empty())&&d[i]<d[q.back()]){
q.pop_back();
}
q.push_back(i);
if (d[i]-d[q.front()]>res)
res=d[i]-d[q.front()];
}
printf("%lld\n",ans+res);
}
}
标签：Even,even,int,Positions,Sum,long,数组,odd,sum From： https://www.cnblogs.com/wegret/p/17020898.html