Odd sum (对本菜鸡来说是个极坑题)

https://codeforces.com/problemset/problem/797/B

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given sequence a1, a2, ..., an of integer numbers of length n. Your task is to find such subsequence that its sum is odd and maximum among all such subsequences. It's guaranteed that given sequence contains subsequence with odd sum.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

You should write a program which finds sum of the best subsequence.

Input

The first line contains integer number n (1 ≤ n ≤ 105).

The second line contains n integer numbers a1, a2, ..., an ( - 104 ≤ ai ≤ 104). The sequence contains at least one subsequence with odd sum.

Output

Print sum of resulting subseqeuence.

Examples

input

4
-2 2 -3 1

output

input

3
2 -5 -3

output

-1

　　求子序列，其和为最大奇数。根据题意，序列内元素是可以随意组合的。
　　题解：：要想求最大，肯定得先把所有正数加起来，为sum,看看他是不是奇数，如果是，直接输出。否则
　　　　　　令sum2=sum,sum1=sum;
　　　　　　对数组排个序；
　　　　　　正数搞完了，不是奇数，所以要对负数下手。但是对负数可不是随便搞的，要知道，sum2每次加一个负数，都会变小。我们的目的是让sum2变成奇数，根据偶数-奇数=奇数以及贪心的思想，
我们需要最大的负奇数，找到后，sum2+=它，即可。
　　　　　　但是刚进行的是一个减的操作，并不能保证它是最大，因为在sum加的过程中，可能会出现奇数，那么sum此时的状态并不一定比sum2小。所以：
　　　　　　　sum1=sum,根据贪心思想，且偶-奇=奇，找到最小正奇数，sum1-=它。
　　　　　　再对sum1,sum2进行一个比较即可，但是，根据样例2，sum1可能为偶，因为sum在加的过程中肯不出现奇数，判断即可了。同理sum2也是。
　　　　坑死我了....
　　　　上代码

#include<iostream>

#include<cstring>

#include<set>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long ll;

#include<map>

const int maxn=1e5+;

int maxx=-2e4+;

int a[maxn];

int main()    //qq as a

{

    int n;

    cin>>n;

    int sum=;

    for(int i=;i<n;i++)

    {

        cin>>a[i];

        if(a[i]>)

            sum+=a[i];

    //    cout<<"sum: "<<sum<<"  a:"<<a[i]<<endl;

    }

    if(sum%!=)

        cout<<sum<<endl;

    else

    {

        sort(a,a+n);

        int sum1=sum;

        for(int i=;i<n;i++)

        {

            if(a[i]>&&a[i]%!=)

            {

                sum1-=a[i];break;

            }

        }

        int sum2=sum;

        for(int i=n-;i>=;i--)

        {

            if(a[i]<&&(-a[i])%!=)

            {

                sum2+=a[i];break;

            }

        }

    //    cout<<sum1<<" "<<sum2<<endl;

        if(sum1%==)

            cout<<sum2<<endl;

        else if(sum2%==)

            cout<<sum1<<endl;

        else if(sum1<sum2)

            cout<<sum2<<endl;

        else

            cout<<sum1<<endl;

    }

    return ;

}

巴特西

Odd sum (对本菜鸡来说是个极坑题)

最新文章

热门文章