D.Maximum Sum on Even Positions
题意
给出一个长度为n<2e5的数组ai
你可以将数组中的一个子串 倒置
使得这个数组中偶数位的sum最大
题解
倒置操作只有偶数长度子串会对最后sum产生影响
奇数长度的子串倒置后原来在偶数位的数仍然在偶数位
奇数长度倒置后原来奇数位的数变为偶数那么就相当于
原来偶数位的sum+(子串中奇数位和-子串中偶数位和)
所以考虑相邻两位两两做差作为一个整体放入新数组中
然后对新数组求最大子段和sub 与原来sum相加更新答案
由于原来数组长度n可能为奇数
所以相邻数两两做差有两种情况 都要考虑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
using namespace std;
typedef long long ll;
const int Max=2e5+5;
const int Mod=1e9+7;
ll data[Max],ndata[2][Max];
/*
*/
int main() {
Turnoff;
int t;cin>>t;
while(t--){
int n;cin>>n;
ll sum=0,osum=0;int cnt1=0,cnt2=0;
for(int i=0;i<n;i++){
cin>>data[i];
if(i&1){
ndata[0][cnt1++]=data[i]-data[i-1];
}
else {
sum+=data[i];
if(i)ndata[1][cnt2++]=data[i-1]-data[i];
}
}
ll minn=0,per=0,sub=0,ans=0;
for(int i=0;i<cnt1;i++){
per+=ndata[0][i];
minn=min(minn,per);
sub=max(sub,per-minn);
}
//cout<<sum<<" "<<sub<<endl;
ans=sum+sub;
per=0;minn=0;
for(int i=0;i<cnt2;i++){
per+=ndata[1][i];
minn=min(minn,per);
sub=max(sub,per-minn);
}
ans=max(ans,sum+sub);
cout<<ans<<endl;
}
}
|