Practice/Google/Leetcode 2098. Subsequence of Size K With the Largest Even Sum

Leetcode 2098. Subsequence of Size K With the Largest Even Sum

CodingMust

Problem

You are given an array of integers nums and an integer k. Your task is to select exactly k elements from the array such that their sum is even and as large as possible.

Return the maximum even sum you can obtain by selecting exactly k elements. If no such even sum is possible, return -1.

Note: A sum is even if it is divisible by 2 (including 0). The same element cannot be selected multiple times.

Requirements

1. Select exactly k elements from the input array
2. The sum of selected elements must be even
3. Among all valid even sums, return the maximum
4. Each element can only be used once
5. Return -1 if no valid even sum exists

Constraints

• 1 ≤ nums.length ≤ 10⁵
• 1 ≤ k ≤ nums.length
• 1 ≤ nums[i] ≤ 10⁹
• Expected time complexity: O(n log n)
• Expected space complexity: O(1) or O(n)

Examples

Example 1:

Input: nums = [4, 1, 5, 3, 1], k = 3 Output: 12 Explanation: Select elements [5, 4, 3]. Their sum is 12, which is even and maximal.

Example 2:

Input: nums = [1, 3, 5], k = 2 Output: 8 Explanation: Select [5, 3]. Sum is 8 (even). We need two odd numbers to get an even sum.

Example 3:

Input: nums = [2, 4, 6], k = 1 Output: 6 Explanation: Select the single largest even number: 6.

Example 4:

Input: nums = [1, 3], k = 2 Output: 4 Explanation: Select both [3, 1] for sum 4 (even).