【题面】

题目描述

给你一个长度为 \(n\) 的序列 \(a\) ，你要从序列中任选若干个数字求和（至少一个），求最终能组成的最大奇数为多少，无法组成输出 \(-1\) 。

输入格式

输入的第一行包含一个正整数 \(n\) 。

第二行一共包含 \(n\) 个整数，分别表示 \(a_1,a_2,\dots,a_n\) 。

输出格式

输出一行一个整数，表示最大奇数的值，无解输出 \(-1\) 。

数据范围

对于 100% 的数据， \(1≤n≤20,{−10^6}≤{a_i}≤{10^6}\) 。

各测试点的附加限制如下表所示：

测试点编号 	n≤ 	特殊性质
1∼2 		1 	n=1
3∼5 		2 	n=2
6∼9 		10 	没有负数
10∼11 		20 	只有奇数个奇数
12∼13 		20 	只有偶数个奇数
14∼15 		20 	没有偶数
16∼17 		20 	没有奇数
18∼20 		20

格式说明

输出时每行末尾的多余空格，不影响答案正确性

输入、输出要求

要求使用「文件输入、输出」的方式解题，输入文件为 odd.in，输出文件为 odd.out

样例输入1

5
1 3 6 5 -2

样例输出1

15

样例解释1

选择 1,3,6,5 组成最大奇数，所以最大奇数为 1+3+6+5=15 ，可以证明没有更大的奇数。

样例输入2

4
2 4 6 8

样例输出2

-1

样例解释2

无法选出任何奇数。

【解析】

知识点：分类讨论、数学。

因为 \(n\) 只有 \(20\) ，相对简单：

1. 如果不想分类讨论，可以直接搜索枚举每个数选/不选，然后对答案为奇数的取 \(max\) ，复杂度 \(O{({2^n}{\cdot}{n})}\) 。

2. 如果考虑分类讨论：

如果没有奇数，肯定直接输出 \(-1\) 。

注意：因为本题 \(a_i\) 可能为负数，那么 \({a_i}%2\) 可能等于 \(-1\) ，所以判断奇数的时候应该使⽤ \({a_i}%2!=0\) 。

根据：
1. 偶数 + 偶数 = 偶数；
2. 奇数 + 奇数 = 偶数
3. 偶数 + 奇数 = 奇数；

如果答案加上⼀个偶数，并不会影响其奇偶性。所以对于所有⾮负偶数，直接累加，计⼊答案。

那么剩下的就是奇数的选择：
1. 因为最终答案要求的是最⼤奇数，所以要选择⾄少 1 个奇数，把最⼤的奇数计⼊答案。
2. 对于剩下的奇数，不能只选⼀个（会使得最终答案变为偶数），所以需要两个一组地选。那么思路就很明显了，如果你要使得答案增加，那就
要让这两个奇数加和为正。
3. 所以对剩下的奇数排序，每次选取最⼤的两个，如果这两个加和⾮负，那就把他们加⼊到答案中。

【参考代码】

sum是summation的缩写，意为求和
cnt是count的缩写，意为计数器
aver是average value，意为平均值

#include <bits/stdc++.h>
using namespace std;
int main() {
	freopen("odd.in", "r", stdin);
	freopen("odd.out", "w", stdout);
	int n;
	int a[25], b[25];
	int sum = 0, cnt = 0;

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (a[i] % 2 != 0) { // 因为存在负数，所以不能用 == 1 进⾏判断
			b[cnt++] = a[i];
		}
		if (a[i] % 2 == 0 && a[i] > 0) {
			sum += a[i];
		}
	}
	if (cnt == 0) {
		cout << -1 << '\n';
	} else {
		sort(b, b + cnt, greater<int>());
		sum += b[0]; // 最少选⼀个奇数
		for (int i = 1; i + 1 < cnt; i += 2) {
			if (b[i] + b[i + 1] >= 0) {
				sum += (b[i] + b[i + 1]);
			}
		}
		cout << sum << '\n';
	}
	return 0;
}