Link

CF1899 C Yarik and Array

Question

给定一个数组，求数组中连续子数组之和的最大值，但要求子数组必须满足：相邻两项奇偶性不同

输出最大总和

定义 \(F[i]\) 为以 \(i\) 为终点的连续子串的最大加和

\(F[i]\) 初始为 \(a[i]\)

如果 \(a[i]\) 和 \(a[i-1]\) 奇偶性不同可以转移

\[F[i]=\max\{F[i],F[i-1]+a[i]\} \]

答案就是 \(\max\{F[i]\}\)

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1ll<<60;
const int maxn=2e5+5;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int F[maxn],a[maxn];
void solve(){
    int N=read(),ans=-INF;
    if(N==1){int x=read();printf("%lld\n",x);return ;}
    for(int i=1;i<=N;i++) F[i]=a[i]=read(); ans=F[1];
    for(int i=2;i<=N;i++){
        if((a[i]&1)^(a[i-1]&1)) {
            F[i]=max(F[i],F[i-1]+a[i]);
        }
        ans=max(ans,F[i]);
    }
    
    printf("%lld\n",ans);
}
signed main(){
    int T=read();
    while(T--)solve();
    return 0;
}