子序列

给定一个长度为 nn 的整数序列 a1,a2,…,an

请你找到一个该序列的子序列，要求：

1. 该子序列的所有元素之和必须是奇数。
2. 在满足条件 1 的前提下，该子序列的所有元素之和应尽可能大。

输出你找到的满足条件的子序列的所有元素之和。

保证至少存在一个满足条件的子序列。

注意，子序列不一定连续。

输入格式

第一行包含一个整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

输出一个整数，表示满足条件的子序列的所有元素之和。

数据范围

前 6 个测试点满足 1≤n≤5。
所有测试点满足 1≤n≤10的5次方，−10的4次方≤ai≤10的4次方。

输入样例1：

4
-2 2 -3 1

输出样例1：

3

输入样例2：

3
2 -5 -3

输出样例2：

-1

我们可以先想一下解题的思路

最大值有三种情况：

1、所有正数加起来是奇数
2、所有正数加起来是偶数，那么就比较减去最小奇正数和加上最大奇负数哪个大
3、如果没有正数那么答案就是最大奇负数

  其中第一种情况和第三种情况是很好解决的，难就难在第二种情况，我昨天编写了两个多小时，思路早就想好了，只差一步了，然后又遇到了在AcWing上面的输出结果和我在C++编译器上面的输出结果不一样（程序一模一样，输入一模一样）的问题，简直烦死我了。

  终于在今天早上，我编了差不多半个多小时，调试了无数次之后，终于发现了问题，原来是数组越界，我本来定义a[n]的，n等于3的时候直接就a[4]去了，然后我将数组数量定位n的最大值，将其中所有的归为0就是了。

我的独创代码：

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int i,int j) 
{
    return i>j;
}
int main()
{
	int n,sum=0,vum=0,num=0,b=0,c=0,i=0,x=0;
	cin>>n;
	int a[1000000];
	for(int i=0;i<1000000;i++)
	  a[i]=0;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		if(a[i]<0)
		  num++;
	}	  
	if(n==1)
	{
		cout<<a[0]; 
		return 0;
	}
	else if(num==n)
	{
		sort(a,a+n,cmp);
		for(int i=0;i<n&&a[i]<0;i++)
		{
			if(a[i]%2==1)
			{
		        cout<<a[0];
		        return 0;
			}
		}
	}
	sort(a,a+n,cmp);
	for(int i=0;i<n&&a[i]>0;i++)
	  sum+=a[i];
	if(sum%2==1)
	{
		cout<<sum;
	}
	else if(sum%2==0)
	{
        sort(a,a+n);
		while(x==0)
		{
		    if(a[i]%2==1)
		    {
		    	b=a[i];
		    	x=1;
			}			
			i++;	
		}
		x=0;
		i=0;
		sort(a,a+n,cmp);
		while(x==0)
		{
		    if(a[i]%2==-1)
		    {
		    	c=a[i];
		    	x=1;
			}		
			i++;	
		}
        int y,z;
		y=sum+c;
		z=sum-b; 
        if(y<z)
          cout<<z;
        else if(y>z)
          cout<<y;
        else
          cout<<z;
	}
}

1、所有正数加起来是奇数
2、如果没有正数那么答案就是最大奇负数

  这两种我们可以单独来看看。

  第一种我们在输入的的时候就可以开始加，判断条件就是for(int i=0;i<n&&a[i]>0;i++)，毕竟我们是来求所有正数的最大值，先判断是不是奇数，然后直接输出就好了，由于是单独判断，结尾时不要忘记加return 0;在这之前，我们一定要把这串数从大到小排序，这样就不会出现一会儿正数一会儿负数的判断了，时间更快一些

  第二种我们可以判断他是不是负数，每一个数都判断，有的话就num++，如果全部都是负数的话，那么num一定会等于数的个数n，接着将这串数从大到小排序，判断条件是for(int i=0;i<n&&a[i]<0;i++),找出其中最大的奇负数，输出就可以了。

  现在简单的两种分析好了，到最复杂的了。

1、所有正数加起来是偶数，那么就比较减去最小奇正数和加上最大奇负数哪个大

  刚开始，要从小到大排序，为什么呢？因为我们要找最小奇正数，从大到小找难免会出现一些错 误，这里我们可以直接用while循环，其实直接用上面那个for循环判断条件也是可以的，找到最小奇正数时停止循环，将最小奇正数保存在一个变量里面。

  最小奇正数找到了 ，要找最大奇负数了，之前是从小到大的排序，现在就要从大到小的排序，因为我们找到是最大奇负数嘛!运用上面的方法，找到最大奇负数，存在一个变量里面。

  最后我们就比较，所有正数的和减去最小奇正数大还是所有正数的和加上最大奇负数谁大就输出谁，如果一样大就随便输出一个就行了。

  终于搞定了这道题，只有中等的难度，但是对于我来说是很难的了，至于第49场周赛的第三题，困难题型，至今我还是做不出来的，现在五一时期，多做些题，多写一些文章。