「力扣挑战赛」心算项目的挑战比赛中，要求选手从 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

思路

  • 排序+统计（优化到极致代码）详情见代码注释

代码

class Solution {
    public int maximumScore(int[] cards, int cnt) {
        int result = 0;
        int[] counts = new int[1001];
        int max = 0;//最大值
        //排序+统计
        for (int card : cards) {
            counts[card]++;
            if (card > max) {
                max = card;
            }
        }
        int sufMinOdd = 1001;//已计算最小奇数
        int sufMinEven = 1002;//已计算最小偶数
        int now = max;//已计算cnt=0时所在位置数
        //计算
        for (int i = max; cnt > 0 && i >= 0; i--) {
            if (counts[i] > 0) {
                if (cnt >= counts[i]) {
                    result += i * counts[i];
                    cnt -= counts[i];
                    counts[i] = 0;
                } else {
                    result += i * cnt;
                    counts[i] -= cnt;
                    cnt = 0;
                }
                if ((i & 1) == 1) {
                    sufMinOdd = i;
                } else {
                    sufMinEven = i;
                }
                now = i;
            }
        }
        //偶数直接返回
        if ((result & 1) == 0) {
            return result;
        }
        //说明后方至少有一个奇数
        int preMaxOdd = 0;//前方最大奇数
        int preMaxEven = 0;//前方最大偶数
        now >>= 1;
        now <<= 1;
        for (int i = now; i > 0; i -= 2) {
            if (counts[i] > 0) {
                preMaxEven = i;
                break;
            }
        }
        for (int i = now + 1; i > 0; i -= 2) {
            if (counts[i] > 0) {
                preMaxOdd = i;
                break;
            }
        }
        //开始判断计算方案
        if (preMaxOdd == 0 && preMaxEven == 0) {//1.前方无奇偶数，没有方案
            return 0;
        } else if (preMaxOdd == 0) {//2.前方无奇数有偶数，只能将前方最大偶数替换后方最小奇数
            result -= sufMinOdd;
            result += preMaxEven;
        } else if (preMaxEven == 0) {//3.前方有奇数无偶数
            if (sufMinEven == 1002) {//3.1说明后方无偶数，无法替换前方奇数
                return 0;
            }
            //3.2后方最小偶数替换前方最大奇数
            result -= sufMinEven;
            result += preMaxOdd;
        } else {//4.前方有奇数有偶数
            if (sufMinEven == 1002) {//4.1后方无偶数，只能将前方最大偶数替换后方最小奇数
                result -= sufMinOdd;
                result += preMaxEven;
            } else if (sufMinOdd - sufMinEven > preMaxEven - preMaxOdd) {//4.2.1 同奇同偶比较大小，同奇>同偶，前方最大奇数替换后方最小偶数
                result -= sufMinEven;
                result += preMaxOdd;
            } else {//4.2.2 同奇<=同偶，前方最大偶数替换后方最小奇数
                result -= sufMinOdd;
                result += preMaxEven;
            }
        }
        return result;
    }
}