problemmediumalgorithmsleetcode-2098leetcode 2098leetcode2098

Subsequence of Size K With the Largest Even Sum

MediumUpdated: Sep 14, 2025
Practice on:
LeetCode

Problem

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.

Examples

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 <= 10^5
  • 0 <= nums[i] <= 10^5
  • 1 <= k <= nums.length

Solution

Method 1 - Greedy + Parity Swap

Intuition

To maximize the sum, pick the k largest numbers. If their sum is even, return it. If odd, try to swap the smallest odd in the k largest with the largest even outside, or the smallest even in the k largest with the largest odd outside, to make the sum even. If not possible, return -1.

Approach

  1. Sort nums in descending order.
  2. Take the k largest numbers as the candidate subsequence.
  3. If their sum is even, return it.
  4. Otherwise, try to swap to make the sum even:
    • Find the smallest odd in the k largest and the largest even outside.
    • Find the smallest even in the k largest and the largest odd outside.
    • If either swap is possible, return the maximum even sum after swap.
    • Otherwise, return -1.

Code

C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int largestEvenSum(vector<int>& nums, int k) {
        sort(nums.rbegin(), nums.rend());
        int n = nums.size();
        int sum = 0;
        int minOdd = 1e9+1, minEven = 1e9+1;
        int maxOdd = -1, maxEven = -1;
        for (int i = 0; i < k; ++i) {
            sum += nums[i];
            if (nums[i] % 2) minOdd = min(minOdd, nums[i]);
            else minEven = min(minEven, nums[i]);
        }
        for (int i = k; i < n; ++i) {
            if (nums[i] % 2) maxOdd = max(maxOdd, nums[i]);
            else maxEven = max(maxEven, nums[i]);
        }
        if (sum % 2 == 0) return sum;
        int ans = -1;
        if (minOdd < 1e9+1 && maxEven != -1)
            ans = max(ans, sum - minOdd + maxEven);
        if (minEven < 1e9+1 && maxOdd != -1)
            ans = max(ans, sum - minEven + maxOdd);
        return ans;
    }
};
// Leetcode signature: int largestEvenSum(vector<int>& nums, int k);
Go
import "sort"
func largestEvenSum(nums []int, k int) int {
    sort.Slice(nums, func(i, j int) bool { return nums[i] > nums[j] })
    n := len(nums)
    sum := 0
    minOdd, minEven := 1<<31-1, 1<<31-1
    maxOdd, maxEven := -1, -1
    for i := 0; i < k; i++ {
        sum += nums[i]
        if nums[i]%2 == 1 {
            if nums[i] < minOdd { minOdd = nums[i] }
        } else {
            if nums[i] < minEven { minEven = nums[i] }
        }
    }
    for i := k; i < n; i++ {
        if nums[i]%2 == 1 {
            if nums[i] > maxOdd { maxOdd = nums[i] }
        } else {
            if nums[i] > maxEven { maxEven = nums[i] }
        }
    }
    if sum%2 == 0 { return sum }
    ans := -1
    if minOdd < 1<<31-1 && maxEven != -1 {
        if sum-minOdd+maxEven > ans { ans = sum-minOdd+maxEven }
    }
    if minEven < 1<<31-1 && maxOdd != -1 {
        if sum-minEven+maxOdd > ans { ans = sum-minEven+maxOdd }
    }
    return ans
}
Java
import java.util.*;
class Solution {
    public int largestEvenSum(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, sum = 0;
        int minOdd = Integer.MAX_VALUE, minEven = Integer.MAX_VALUE;
        int maxOdd = -1, maxEven = -1;
        for (int i = 0; i < k; ++i) {
            int v = nums[n-1-i];
            sum += v;
            if (v % 2 == 1) minOdd = Math.min(minOdd, v);
            else minEven = Math.min(minEven, v);
        }
        for (int i = k; i < n; ++i) {
            int v = nums[n-1-i];
            if (v % 2 == 1) maxOdd = Math.max(maxOdd, v);
            else maxEven = Math.max(maxEven, v);
        }
        if (sum % 2 == 0) return sum;
        int ans = -1;
        if (minOdd < Integer.MAX_VALUE && maxEven != -1)
            ans = Math.max(ans, sum - minOdd + maxEven);
        if (minEven < Integer.MAX_VALUE && maxOdd != -1)
            ans = Math.max(ans, sum - minEven + maxOdd);
        return ans;
    }
}
Kotlin
fun largestEvenSum(nums: IntArray, k: Int): Int {
    val arr = nums.sortedDescending()
    var sum = 0
    var minOdd = Int.MAX_VALUE; var minEven = Int.MAX_VALUE
    var maxOdd = -1; var maxEven = -1
    for (i in 0 until k) {
        sum += arr[i]
        if (arr[i] % 2 == 1) minOdd = minOf(minOdd, arr[i])
        else minEven = minOf(minEven, arr[i])
    }
    for (i in k until arr.size) {
        if (arr[i] % 2 == 1) maxOdd = maxOf(maxOdd, arr[i])
        else maxEven = maxOf(maxEven, arr[i])
    }
    if (sum % 2 == 0) return sum
    var ans = -1
    if (minOdd < Int.MAX_VALUE && maxEven != -1)
        ans = maxOf(ans, sum - minOdd + maxEven)
    if (minEven < Int.MAX_VALUE && maxOdd != -1)
        ans = maxOf(ans, sum - minEven + maxOdd)
    return ans
}
Python
def largestEvenSum(nums, k):
    nums = sorted(nums, reverse=True)
    topk = nums[:k]
    rest = nums[k:]
    s = sum(topk)
    if s % 2 == 0:
        return s
    min_odd = min((x for x in topk if x % 2), default=None)
    min_even = min((x for x in topk if x % 2 == 0), default=None)
    max_odd = max((x for x in rest if x % 2), default=None)
    max_even = max((x for x in rest if x % 2 == 0), default=None)
    ans = -1
    if min_odd is not None and max_even is not None:
        ans = max(ans, s - min_odd + max_even)
    if min_even is not None and max_odd is not None:
        ans = max(ans, s - min_even + max_odd)
    return ans
Rust
pub fn largest_even_sum(nums: Vec<i32>, k: i32) -> i32 {
    let mut nums = nums;
    nums.sort_unstable_by(|a, b| b.cmp(a));
    let k = k as usize;
    let topk = &nums[..k];
    let rest = &nums[k..];
    let s: i32 = topk.iter().sum();
    if s % 2 == 0 { return s; }
    let min_odd = topk.iter().filter(|&&x| x % 2 != 0).min().copied();
    let min_even = topk.iter().filter(|&&x| x % 2 == 0).min().copied();
    let max_odd = rest.iter().filter(|&&x| x % 2 != 0).max().copied();
    let max_even = rest.iter().filter(|&&x| x % 2 == 0).max().copied();
    let mut ans = -1;
    if let (Some(mo), Some(me)) = (min_odd, max_even) {
        ans = ans.max(s - mo + me);
    }
    if let (Some(me), Some(mo)) = (min_even, max_odd) {
        ans = ans.max(s - me + mo);
    }
    ans
}
TypeScript
function largestEvenSum(nums: number[], k: number): number {
    nums.sort((a, b) => b - a);
    const topk = nums.slice(0, k);
    const rest = nums.slice(k);
    const s = topk.reduce((a, b) => a + b, 0);
    if (s % 2 === 0) return s;
    const minOdd = Math.min(...topk.filter(x => x % 2 === 1), Infinity);
    const minEven = Math.min(...topk.filter(x => x % 2 === 0), Infinity);
    const maxOdd = Math.max(...rest.filter(x => x % 2 === 1), -Infinity);
    const maxEven = Math.max(...rest.filter(x => x % 2 === 0), -Infinity);
    let ans = -1;
    if (minOdd !== Infinity && maxEven !== -Infinity)
        ans = Math.max(ans, s - minOdd + maxEven);
    if (minEven !== Infinity && maxOdd !== -Infinity)
        ans = Math.max(ans, s - minEven + maxOdd);
    return ans;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)

Comments