「力扣挑战赛」心算项目的挑战比赛中，要求选手从 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^5 - 1 <= cards[i] <= 1000

1.前置知识

由一些基本的数论知识可得：

要想几个数之和为偶数，这几个数必须满足的条件是：任意个偶数，还有偶数个奇数。

2.思路：

先将卡牌数组进行排序
不管是否满足卡牌之和为偶数，将最大的cnt张牌之和存入变量sum，此时的sum是绝对最大值，但不一定是偶数
在上面拿到的卡牌中，找到最小的奇数和最小的偶数，分别存入变量odd，even
1. 如果此时sum正好是偶数，那么就直接返回sum
2. 如果此时sum是奇数，那么继续进行下面的处理
遍历剩下的数，维护一个最大值max，那么接下来的策略就是：换牌，分为两种情况：
1. 丢奇拿偶：将最小的奇数替换成当前的偶数。前提：必须存在最小的奇数
  max = Math.max(max,sum + cards[i] - odd);
2. 丢偶拿奇：将最小的偶数替换成当前的奇数。前提：必须存在最小的偶数
  max = Math.max(max,sum + cards[i] - even);

根据上面这个思路，就可以写出如下代码：

public int maxmiumScore(int[] cards, int cnt) {
        int odd = Integer.MAX_VALUE;
        int even = Integer.MAX_VALUE;
        int sum = 0;
        //排序
        Arrays.sort(cards);
        //倒序遍历最后cnt张牌，即最大的几张牌
        for (int i = cards.length - 1; i >= cards.length - cnt; i--) {
            //存入最小的奇数和偶数
            if((cards[i] & 1)==0){
                even = cards[i];
            }else{
                odd = cards[i];
            }
            //求和
            sum += cards[i];
        }
        //如果和正好是偶数，那就直接返回这个数
        if((sum & 1) == 0){
            return sum;
        }
        int max = 0;
        //遍历剩下的卡牌
        for(int i = cards.length - cnt - 1; i >= 0; i--){
            if((cards[i] & 1) == 0 && odd != Integer.MAX_VALUE){
                //丢奇拿偶
                max = Math.max(max,sum + cards[i] - odd);
            }else if(((cards[i] & 1) == 1 && even != Integer.MAX_VALUE)) {
                //丢偶拿奇
                max = Math.max(max,sum + cards[i] - even);
            }
        }
        return max;
    }

3.优化

在我们需要换牌凑偶的时候，sum必是奇数，也就是说选择的牌中必然存在奇数，所以并不再需要判断最小的奇数是否存在了，另外，我们并不需要每次循环都判断even != Integer.MAX_VALUE，因为even并不会发生改变，我们只需要用一个变量在外面判断好存起来就可以了。
让我们再想想有没有什么可以优化的点，我们之前已经将卡牌进行了排序，直觉告诉我们，我们并不需要遍历剩下的全部数字。我们不妨理一下可能出现的几种情况：

如果最大的cnt张卡牌中全部都是奇数，由于我们是从大到小有顺序遍历的，那么我们只需要找到一个偶数，把最小的奇数换掉，就可以break掉了
如果最大的cnt张卡牌中有奇有偶，那么我们只需要换一次奇数，一次偶数就可以了。这是因为我们是由大到小进行遍历的，如果之前换过一次奇数或者偶数，那么接下来的奇数或者偶数都是比之前小的，不需要再进行尝试替换了。
并且，如果说odd<even 说明最小奇数小于最小偶数，那么如果我们找到了一个偶数，就可以直接替换break了。反之，如果odd>even,那我们只需要找到一个奇数就可以break了。

下面是改进后的代码：

public int maxmiumScore(int[] cards, int cnt) {
        int odd = Integer.MAX_VALUE;
        int even = Integer.MAX_VALUE;
        int sum = 0;
        Arrays.sort(cards);
        for (int i = cards.length - 1; i >= cards.length - cnt; i--) {
            if((cards[i] & 1)==0){
                even = cards[i];
            }else{
                odd = cards[i];
            }
            sum += cards[i];
        }
        if((sum & 1) == 0){
            return sum;
        }
        int max = 0;
        boolean oddFlag = false;
        boolean evenFlag = false;
        boolean evenNotExist = even == Integer.MAX_VALUE;
        boolean o2e = odd < even;
        for(int i = cards.length - cnt - 1; i >= 0; i--){
            if(!oddFlag &&(cards[i] & 1) == 0){
                max = Math.max(max,sum + cards[i] - odd);
                oddFlag = true;
                if(evenFlag || !o2e || evenNotExist){
                    break;
                }
            }else if(!evenFlag && (cards[i] & 1) == 1 && !evenNotExist) {
                max = Math.max(max,sum + cards[i] - even);
                evenFlag = true;
                if(oddFlag || o2e){
                    break;
                }
            }
        }
        return max;
    }

LCP 40-心算挑战

1.前置知识

2.思路：

3.优化