添加链接描述
数论：
三种情况：
1.找到最大的数，如果这个数是<=0，说明都是负数或0，找到最大的负奇数既答案
2.最大的正数和为奇数，为答案，
3.最大的正数和为偶数，判断减去最小正奇数和加上最大负奇数哪个大为答案；
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int arr[N];
int sum=0,mx_ne=-0x3f3f3f3f,mi_po=0x3f3f3f3f,mx_num=-0x3f3f3f3f;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
if(arr[i]>=0)sum+=arr[i];
if(arr[i]&1){
if(arr[i]<=0){
mx_ne=max(mx_ne,arr[i]);
}
else {
mi_po=min(mi_po,arr[i]);
}
}
mx_num=max(mx_num,arr[i]);
}
if(sum&1){
cout<<sum<<"\n";
}
else if(mx_num<=0){
cout<<mx_ne<<"\n";
}
else {
int ans=max(sum+mx_ne,sum-mi_po);
cout<<ans<<"\n";
}
return 0;
}
线性dp
dp【i】【j】表示选取前i个结果为奇数或负数的最大值
初始化为最小
dp【0][0]=0
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int dp[N][3],arr[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
memset(dp,-0x3f,sizeof dp);
dp[0][0]=0;
for(int i=1;i<=n;i++){
int x=arr[i];
dp[i][0]=max(dp[i-1][0],dp[i-1][x&1]+x);
dp[i][1]=max(dp[i-1][1],dp[i-1][(x&1)^1]+x);
}
cout<<dp[n][1]<<"\n";
return 0;
}
