题目：
「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N 张卡牌中选出 cnt 张卡牌，若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。 给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。
示例 1：
输入：
cards = [1,2,8,9], cnt = 3输出：
18解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。
示例 2：
输入：
cards = [3,3,1], cnt = 1输出：
0解释：不存在获取有效得分的卡牌方案。
提示：
1 <= cnt <= cards.length <= 10^51 <= cards[i] <= 1000
暴力回溯，寻找所有可能卡牌方案
思路：
从 N 中卡牌中寻找到 cnt 张卡牌，然后判断他们的和是不是偶数，求最大的偶数
那么就通过回溯枚举所有可能组合方案，在枚举过程中记录当前枚举出的总和，那么就可以减少存储卡牌方案的空间复杂度。
代码：
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
int ans = 0;
void backTrack(vector<int>& cards, int cnt, int start, int curSum) {
if (path.size() == cnt) {
if (curSum % 2 == 0) {
ans = max(ans, curSum);
}
return;
}
for (int i = start; i < cards.size(); i++) {
curSum += cards[i];
path.push_back(cards[i]);
backTrack(cards, cnt, i + 1, curSum);
curSum -= cards[i];
path.pop_back();
}
}
int maxmiumScore(vector<int>& cards, int cnt) {
backTrack(cards, cnt, 0, 0);
return ans;
}
};
贪心优化
思路：
回溯算法没有利用最大偶数这个条件
想要最大偶数，那么必然从大的数里面选，然后求和
那么限制点就是和为偶数，这个点就是贪心要处理的核心点
贪心点要考虑的问题在于，如果最大的 cnt 个数和不是偶数，该替换哪个数字。
由于奇数偶数只有两种情况，所以这是可以枚举出来的，具体思路见下文：
为了选取尽量大的数，将 cards 从大到小排序，并累加前 cnt 个数，记作 s。
分类讨论：
如果 s 是偶数，这是我们能得到的最大得分，直接返回 s。
如果 s 是奇数，那么可以：
从前 cnt 个数中去掉一个最小的奇数，从后 n−cnt 中加进来一个最大的偶数，这样得分就变成偶数了。
从前 cnt 个数中去掉一个最小的偶数，从后 n−cnt 中加进来一个最大的奇数，这样得分就变成偶数了。
两种情况取最大值。
讨论 s 是奇数时的细节。
在前 cnt 个数中，x=cards[cnt−1] 要么是最小的奇数，要么是最小的偶数，所以 x 一定会被替换掉。
在前 cnt 个数中的另一个被替换的数，就是奇偶性和 x 不同的最小元素了。
代码：
class Solution {
public:
int maxmiumScore(vector<int>& cards, int cnt) {
ranges::sort(cards, greater());
int s = reduce(cards.begin(), cards.begin() + cnt, 0);
if (s % 2 == 0) {
return s;
}
auto replace_sum = [&](int x) -> int {
for (int i = cnt; i < cards.size(); i++) {
if (cards[i] % 2 != x % 2) {
return s - x + cards[i];
}
}
return 0;
};
int x = cards[cnt - 1];
int ans = replace_sum(x);
for (int i = cnt - 2; i >= 0; i--) {
if (cards[i] % 2 != x % 2) {
ans = max(ans, replace_sum(cards[i]));
break;
}
}
return ans;
}
};