Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

LeetCode 200 simple questions

### Topic describes

In the challenge contest of the mental arithmetic project, contestants are required to choose CNT cards from N cards. If the sum of the CNT cards is even, the contestant’s score is “valid” and the score is the sum of the CNT cards. Given array cards and CNT, where cards[I] represents the number on the ith card. Please calculate the maximum valid score for the contestant. Returns 0 if there is no card scheme for obtaining valid points.

Example 1:

Input: cards = [1,2,8,9]; CNT = 3 Output: 18

Example 2:

Input: cards = [3,3,1]; CNT = 1 output: 0 description: there is no card scheme to obtain valid scores.

### prompt

• `1 <= cnt <= cards.length <= 10^5`
• `1 <= cards[i] <= 1000`

### Their thinking

If oddcount represents the number of odd cards, oddcount must be an even number. Then cnT-ODdcount has even cards. To get the maximum combination, we just need the sum of the even numbers and the sum of the odd numbers to be maximum. Code implementation: cards in descending order, traversing the value of cards, respectively, the construction of odd and even prefix and array ODD_NUMs, even_NUMS. Then take the value of even subscript from the odd prefix and array ODd_nums. At this time, the number of even cards is CNT-ODdcount. On the premise that the number is ≥0 and less than the array length, the maximum combination in the traversal process is saved.

``````    def maxmiumScore(self, cards, cnt) :
""" :type cards: List[int] :type cnt: int :rtype: int """
cards.sort(reverse=True)
odd_nums, even_nums = [0], [0]  # prefix and array (offset one unit to the right)
for num in cards:
if num & 1:
odd_nums.append(odd_nums[-1] + num)
else:
even_nums.append(even_nums[-1] + num)

res = 0
# Take an even number of odd numbers from the original sequence
for oddcount in range(0.len(odd_nums), 2) :if 0 <= cnt - oddcount < len(even_nums):
res = max(res, odd_nums[oddcount] + even_nums[cnt - oddcount])  # is preceded by the largest number
return res
Copy the code``````

Clocked in today, the current progress 4/200.