Subsequence of Size K With the Largest Even Sum

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,1,5,3,1], k = 3

› Output: 12

💡 Note: Select [4,5,3] which gives sum = 12 (even). This is the largest possible even sum for k=3 elements.

Example 2 — Need Adjustment

$ Input: nums = [4,1,5,3,1], k = 1

› Output: 4

💡 Note: Select [4] which gives sum = 4 (even). The largest single element that gives an even sum.

Example 3 — No Even Sum Possible

$ Input: nums = [1,3,5], k = 3

› Output: -1

💡 Note: All elements are odd, so any subsequence of size 3 will have an odd sum (odd+odd+odd=odd).

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ k ≤ nums.length
-10⁵ ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array [4,1,5,3,1] with k=3

Process

Find k elements that give maximum even sum

Output

Return 12 (from selecting 4,5,3)

Key Takeaway

🎯 Key Insight: Use greedy selection of largest elements, then adjust parity by smart swapping to ensure an even sum

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Facebook 12

The key insight is that to get an even sum, we need an even count of odd numbers. The greedy approach sorts elements and selects the k largest, then adjusts by swapping elements to ensure an even sum while maximizing the total. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Even/Odd Adjustment	O(n log n)	O(1)	Sort elements, greedily select k largest, then adjust to make sum even
Brute Force - Try All Combinations	O(C(n,k) × k)	O(k)	Generate all possible subsequences of size k and find maximum even sum

Greedy with Even/Odd Adjustment — Algorithm Steps

Sort array in descending order
Take k largest elements
If sum is odd, find optimal even/odd swap to maximize even sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort and Select

Take k largest elements

Check Sum Parity

If odd, find best swap

Optimize

Replace to maximize even sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)b - *(int*)a);
}

long long solution(int* nums, int numsSize, int k) {
    if (k > numsSize) {
        return -1;
    }
    
    qsort(nums, numsSize, sizeof(int), compare);
    
    // Take k largest elements
    long long currentSum = 0;
    for (int i = 0; i < k; i++) {
        currentSum += nums[i];
    }
    
    if (currentSum % 2 == 0) {
        return currentSum;
    }
    
    // Sum is odd, need to make it even
    long long maxEvenSum = -1;
    
    // Try replacing smallest odd in selected with largest even in remaining
    for (int i = k - 1; i >= 0; i--) {
        if (nums[i] % 2 == 1) {
            for (int j = k; j < numsSize; j++) {
                if (nums[j] % 2 == 0) {
                    long long newSum = currentSum - nums[i] + nums[j];
                    if (maxEvenSum == -1 || newSum > maxEvenSum) {
                        maxEvenSum = newSum;
                    }
                    break;
                }
            }
            break;
        }
    }
    
    // Try replacing smallest even in selected with largest odd in remaining
    for (int i = k - 1; i >= 0; i--) {
        if (nums[i] % 2 == 0) {
            for (int j = k; j < numsSize; j++) {
                if (nums[j] % 2 == 1) {
                    long long newSum = currentSum - nums[i] + nums[j];
                    if (maxEvenSum == -1 || newSum > maxEvenSum) {
                        maxEvenSum = newSum;
                    }
                    break;
                }
            }
            break;
        }
    }
    
    return maxEvenSum;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line, "[,] \n");
    while (token != NULL && numsSize < 100) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,] \n");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%lld\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Dominated by sorting the input array

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

32.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Even/Odd Adjustment — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler