博客

题目链接：

http://codeforces.com/contest/797/problem/B


题意：给你一个长度为n的序列，让你求他的子序列的最大奇数和是多少，输出这个最大的奇数和

解析：首先这个序列里所有的正数肯定是要的，如果所有正数的和是奇数的话那么直接就是答案了，如果和为偶数，那么就有两种情况，减去最大的奇数，或者加上最大的负奇数，然后两者比较下大小，输出较大的即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
const int inf = 0x7fffffff;
int a[maxn];
int odd[maxn];
int even[maxn];
int main(void)
{
    int n;
    scanf("%d",&n);
    int cnt1 = 0,cnt2 = 0;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]%2)
            odd[cnt1++] = a[i];
        else
            even[cnt2++] = a[i];
    }
    int sum = 0;
    int t1 = -inf,t2 = inf;
    for(int i=cnt1-1;i>=0;i--)
    {
        if(odd[i]<0)
            t1 = max(odd[i],t1);
        else
        {
            t2 = min(t2,odd[i]);
            sum += odd[i];
        }
    }
    for(int i=cnt2-1;i>=0;i--)
    {
        if(even[i]>0)
            sum += even[i];
    }
    if(sum%2)
        printf("%d\n",sum);
    else
        printf("%d\n",max(sum+t1,sum-t2));
    return 0;
}