Problem Description

You need to find the largest possible even sum from a subsequence of an integer array nums that has exactly k elements.

Given:

• An integer array nums
• An integer k

Task:

• Select exactly k elements from nums (maintaining their relative order as a subsequence)
• Calculate the sum of these k elements
• Find the maximum sum that is even
• Return this maximum even sum, or -1 if no even sum is possible

A subsequence means you can pick elements from the original array by skipping some elements, but you cannot change the order of the elements you pick. For example, from [1,2,3,4], you can pick [1,3,4] as a subsequence, but not [3,1,4].

The solution approach sorts the array first and greedily selects the largest k numbers. If their sum is odd, it tries to make it even by:

1. Replacing the smallest even number in the selected k with the largest odd number from the remaining elements
2. Replacing the smallest odd number in the selected k with the largest even number from the remaining elements

The algorithm chooses whichever replacement gives the larger even sum, or returns -1 if no even sum is achievable.

Intuition

Since we're looking for a subsequence (not a subarray), the order of elements doesn't matter for calculating the sum. This gives us the freedom to sort the array, which immediately suggests a greedy approach.

To maximize the sum, we naturally want to pick the k largest numbers. After sorting, these would be the last k elements. If their sum is even, we're done - this is the maximum possible even sum.

But what if the sum of the k largest numbers is odd? We need to make it even somehow.

The key insight is that to change a sum from odd to even (or vice versa), we need to either:

• Add/subtract an odd number
• Add/subtract an even number that changes the parity

Since we must maintain exactly k elements, we can't just add or remove - we need to replace. This means swapping one element from our selected k with one from the remaining n-k elements.

To keep the sum as large as possible while making it even, we want to:

1. Remove the smallest element from our selection
2. Add the largest element from the remaining pool
3. Ensure this swap changes the parity from odd to even

This leads to two scenarios:

• If we remove an even number (the smallest even in our k), we must add an odd number (the largest odd from remaining) to change parity
• If we remove an odd number (the smallest odd in our k), we must add an even number (the largest even from remaining) to change parity

We try both swaps and pick whichever gives us the larger even sum. If neither swap is possible (e.g., all k selected numbers are odd and all remaining are odd too), then no even sum exists and we return -1.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows the greedy strategy with these steps:

Step 1: Sort the array

nums.sort()

This allows us to easily identify the largest k numbers and work with them.

Step 2: Calculate initial sum of largest k numbers

ans = sum(nums[-k:])

We take the last k elements after sorting, which are the largest ones.

Step 3: Check if sum is already even

if ans % 2 == 0:
    return ans

If the sum is even, we've found our answer immediately.

Step 4: Find replacement candidates from remaining elements

mx1 = mx2 = -inf
for x in nums[: n - k]:
    if x & 1:  # if x is odd
        mx1 = x
    else:      # if x is even
        mx2 = x

We iterate through the first n-k elements (those not selected) to find:

• mx1: the largest odd number
• mx2: the largest even number

Since the array is sorted, the last occurrence of each type will be the maximum.

Step 5: Find elements to replace from selected k numbers

mi1 = mi2 = inf
for x in nums[-k:][::-1]:
    if x & 1:  # if x is odd
        mi2 = x
    else:      # if x is even
        mi1 = x

We iterate through the selected k numbers in reverse order to find:

• mi1: the smallest even number
• mi2: the smallest odd number

The reverse iteration [::-1] ensures we find the smallest values first (since the array is sorted).

Step 6: Calculate possible even sums

ans = max(ans - mi1 + mx1, ans - mi2 + mx2, -1)

We consider two possible swaps:

1. Replace smallest even (mi1) with largest odd (mx1): ans - mi1 + mx1
2. Replace smallest odd (mi2) with largest even (mx2): ans - mi2 + mx2

Both swaps change the parity from odd to even. We take the maximum of these two options and -1.

Step 7: Return result

return -1 if ans < 0 else ans

If ans is negative (which happens when no valid swap exists because mx1 or mx2 remained at -inf, or mi1 or mi2 remained at inf), we return -1. Otherwise, we return the maximum even sum found.

The time complexity is O(n log n) due to sorting, and the space complexity is O(1) as we only use a few variables.

Example Walkthrough

Let's trace through the algorithm with nums = [4, 1, 5, 3, 1] and k = 3.

Step 1: Sort the array

• After sorting: nums = [1, 1, 3, 4, 5]

Step 2: Select the k largest numbers

• The 3 largest numbers are the last 3 elements: [3, 4, 5]
• Initial sum: 3 + 4 + 5 = 12

Step 3: Check if sum is even

• 12 % 2 = 0, so the sum is already even
• Return 12 immediately

Let's try another example where we need to make adjustments: nums = [2, 3, 8, 7, 1] and k = 3.

Step 1: Sort the array

• After sorting: nums = [1, 2, 3, 7, 8]

Step 2: Select the k largest numbers

• The 3 largest numbers: [3, 7, 8]
• Initial sum: 3 + 7 + 8 = 18 (even, so return 18)

Let's try one more where the initial sum is odd: nums = [1, 2, 3, 4] and k = 2.

Step 1: Sort the array

• Already sorted: nums = [1, 2, 3, 4]

Step 2: Select the k largest numbers

• The 2 largest numbers: [3, 4]
• Initial sum: 3 + 4 = 7 (odd)

Step 3: Find replacement candidates from remaining elements

• Remaining elements (not in our k selection): [1, 2]
• Largest odd from remaining: mx1 = 1
• Largest even from remaining: mx2 = 2

Step 4: Find elements to replace from selected k

• Selected elements: [3, 4]
• Smallest even from selected: mi1 = 4
• Smallest odd from selected: mi2 = 3

Step 5: Calculate possible swaps

• Option 1: Replace even 4 with odd 1: 7 - 4 + 1 = 4 (even)
• Option 2: Replace odd 3 with even 2: 7 - 3 + 2 = 6 (even)
• Maximum even sum: max(4, 6) = 6

Step 6: Return result

• Return 6

The algorithm correctly identifies that swapping 3 with 2 gives us the maximum even sum of 6 from selecting exactly 2 elements.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array. This is dominated by the sorting operation nums.sort() which uses Timsort algorithm with O(n × log n) complexity. The subsequent operations include:

• Computing sum of last k elements: O(k)
• First loop through nums[:n-k]: O(n-k)
• Second loop through nums[-k:][::-1]: O(k)

Since k ≤ n, all these operations are O(n), which is dominated by the sorting complexity.

The space complexity is O(log n). The sorting algorithm uses O(log n) space for the recursion stack in the worst case. The slicing operations nums[:n-k] and nums[-k:][::-1] create new lists, but in Python's Timsort implementation, the sorting itself requires O(log n) auxiliary space which dominates. The variables ans, mx1, mx2, mi1, mi2 use constant O(1) space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding Subsequence vs Subset

A critical pitfall is confusing subsequence with subset. The problem states we need a subsequence, which maintains relative order, but the solution sorts the array and picks any k elements. This violates the subsequence constraint.

The Issue: After sorting, we're selecting the largest k elements regardless of their original positions, effectively treating this as a subset problem rather than a subsequence problem.

Example:

• Original array: [4, 1, 5, 3, 1], k = 3
• After sorting: [1, 1, 3, 4, 5]
• Solution picks: [3, 4, 5] (largest 3)
• But [3, 4, 5] might not be a valid subsequence of the original [4, 1, 5, 3, 1]

2. Edge Case: Insufficient Elements of Required Parity

The algorithm assumes we can always make swaps, but there might be cases where:

• All k selected elements are odd and there are no even elements in the remaining array
• All k selected elements are even and there are no odd elements in the remaining array

Example:

• Array: [1, 3, 5, 7, 9], k = 3
• Selected: [5, 7, 9] (sum = 21, odd)
• No even numbers available to swap in
• The code would correctly return -1, but the logic might not be immediately clear

3. Incorrect Infinity Handling

When no valid swap candidate exists, the variables remain at infinity/negative infinity, leading to calculations like ans - inf which results in -inf. While the code handles this by checking if ans < 0, this approach is fragile.

Better Solution for Subsequence Problem: If we need to maintain subsequence order, we should use dynamic programming:

def largestEvenSum(self, nums: List[int], k: int) -> int:
    n = len(nums)
    # dp[i][j][parity] = max sum using first i elements, selecting j elements, with sum parity (0=even, 1=odd)
    dp = [[[-1, -1] for _ in range(k + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 0  # Base case: 0 elements selected, sum is 0 (even)
  
    for i in range(1, n + 1):
        for j in range(k + 1):
            # Don't take current element
            dp[i][j][0] = dp[i-1][j][0]
            dp[i][j][1] = dp[i-1][j][1]
          
            # Take current element if possible
            if j > 0:
                curr_parity = nums[i-1] % 2
                for prev_parity in [0, 1]:
                    if dp[i-1][j-1][prev_parity] != -1:
                        new_sum = dp[i-1][j-1][prev_parity] + nums[i-1]
                        new_parity = (prev_parity + curr_parity) % 2
                        dp[i][j][new_parity] = max(dp[i][j][new_parity], new_sum)
  
    return dp[n][k][0]  # Return max even sum with k elements

4. Optimization Assumption Error

The greedy approach assumes that taking the k largest numbers and then making minimal adjustments will yield the optimal result. However, for subsequences, this isn't necessarily true as we're constrained by order.

Counter-example:

• Array: [10, 2, 3, 7, 5], k = 3
• Greedy after sort might pick [7, 5, 10] = 22 (even)
• But the valid subsequence [10, 2, 7] = 19 (odd) or [10, 3, 5] = 18 (even) might be the only options