You are given an integer array nums and an integer k. Find the largest even sum of any subsequence of nums that has a length of k.
Return this sum, or -1 if such a sum does not exist.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [4,1,5,3,1], k = 3
Output: 12
Explanation:
The subsequence with the largest possible even sum is [4,5,3]. It has a sum of 4 + 5 + 3 = 12.
Example 2:
Input: nums = [4,6,2], k = 3
Output: 12
Explanation:
The subsequence with the largest possible even sum is [4,6,2]. It has a sum of 4 + 6 + 2 = 12.
Example 3:
Input: nums = [1,3,5], k = 1
Output: -1
Explanation:
No subsequence of nums with length 1 has an even sum.
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 105
1 <= k <= nums.length
Solutions
Solution 1: Greedy + Sorting
We notice that the problem involves selecting a subsequence, so we can consider sorting the array first.
Next, we greedily select the largest $k$ numbers. If the sum of these numbers is even, we directly return this sum $ans$.
Otherwise, we have two greedy strategies:
Among the largest $k$ numbers, find the smallest even number $mi1$, and then among the remaining $n - k$ numbers, find the largest odd number $mx1$. Replace $mi1$ with $mx1$. If such a replacement exists, then the sum after replacement $ans - mi1 + mx1$ is guaranteed to be even;
Among the largest $k$ numbers, find the smallest odd number $mi2$, and then among the remaining $n - k$ numbers, find the largest even number $mx2$. Replace $mi2$ with $mx2$. If such a replacement exists, then the sum after replacement $ans - mi2 + mx2$ is guaranteed to be even.
We take the largest even sum as the answer. If no even sum exists, return $-1$.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the array.