最大子序列和

整理日期按学习顺序编排，不代表原始发表时间。实际整理于 2026-10-23。

难度为阅读建议，可从 ACM 学习索引 按阶段阅读。

题目描述：给定一个序列，数有正有负，你需要选出一个子序列（不能为空）使你得到的和最大，对于选出来的子序列应该满足相邻数之间奇偶性不同，输出可以得到的最大和

没怎么改的std

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"

const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
int dp[N][3];

void solve(){
	cin>>n;
	bool flag=false;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>=0)flag=true;
	}
	if(flag){
	for(int i=1;i<=n;i++){
		int u=(a[i]%2+2)%2;
		//前i个数中以u这种数结尾的最大子序列和
		//int tmp=max(dp[i-1][u],dp[i-1][!u]);
		dp[i][u]=max(dp[i-1][!u]+a[i],dp[i-1][u]);
		dp[i][!u]=dp[i-1][!u];
		// cerr<<i<<" "<<u<<" "<<dp[i][u]<<endl;
		// cerr<<i<<" "<<!u<<" "<<dp[i][u]<<endl;
	}
	int ans=max(dp[n][0],dp[n][1]);
	cout<<ans<<endl;}
	else {
		cout<<*max_element(a+1,a+1+n)<<endl;
	}
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
 cin>>t;

    while (t--) {
solve();
    }
    return 0;
}