Subsequence of Size K With the Largest Even Sum

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:

1
2
3
4


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:

1
2
3
4


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:

1
2
3
4


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

Sort nums in descending order.
Take the k largest numbers as the candidate subsequence.
If their sum is even, return it.
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


#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);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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)
⏰ Time complexity: O(nnnxxxnnn)
🧺 Space complexity: O(nnnxxx)

Problem#

Examples#

Solution#

Method 1 - Greedy + Parity Swap#

Intuition#

Approach#

Code#

Complexity#