题目链接
题目大意
可以最多翻转一次连续的数组（即子串）求这个数组下标为偶数的和的最大值（数组下标以0开始）
题目思路
首先观察发现翻转奇数个数元素没用，翻转偶数才能改变下标奇偶
和类似于求最大连续子段一样，但是这个可能是从0开始翻转，也可能从1开始翻转
代码
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int maxn
=1e6+5;
const int mod
=1e9+7;
int t
,n
,a
[maxn
];
int main(){
scanf("%d",&t
);
while(t
--){
ll ans
=0;
scanf("%d",&n
);
for(int i
=0;i
<=n
-1;i
++){
scanf("%d",&a
[i
]);
if(i
%2==0){
ans
+=a
[i
];
}
}
ll pre1
=0,pre2
=0,ma1
=0,ma2
=0;
for(int i
=0;i
<=n
-2;i
+=2){
pre1
+=(a
[i
+1]-a
[i
]);
if(pre1
<0){
pre1
=0;
}
ma1
=max(ma1
,pre1
);
}
for(int i
=1;i
<=n
-2;i
+=2){
pre2
+=(a
[i
]-a
[i
+1]);
if(pre2
<0){
pre2
=0;
}
ma2
=max(ma2
,pre2
);
}
ans
+=max(ma1
,ma2
);
printf("%lld\n",ans
);
}
return 0;
}
