Watch 2 video solutions for Subsequence of Size K With the Largest Even Sum, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Programming Live with Larry has 588 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1050 <= nums[i] <= 1051 <= k <= nums.lengthProblem Overview: You are given an integer array and an integer k. Select a subsequence of exactly k elements such that their total sum is even and as large as possible. If no such subsequence exists, return -1.
Approach 1: Brute Force Enumeration (Exponential Time)
Generate every subsequence of size k, compute its sum, and track the largest sum that is even. This can be implemented using recursion or bitmask enumeration. The method checks C(n, k) combinations, giving O(C(n,k) * k) time complexity and O(k) auxiliary space for the current subset. It works only for very small arrays and is mainly useful for validating logic or understanding the constraint that the final sum must be even.
Approach 2: Greedy + Sorting (O(n log n))
The optimal strategy starts by sorting the array in descending order so the largest values are considered first. Select the top k numbers and compute their sum. If the sum is already even, this is the best possible result because replacing any element would reduce the total. If the sum is odd, adjust the selection using parity swaps.
Track the smallest odd and smallest even number inside the chosen k elements, and the largest odd and largest even number outside the selection. To fix an odd sum, perform one of two swaps: replace a chosen odd with an outside even, or replace a chosen even with an outside odd. Both swaps flip the parity of the total sum. Compute the resulting sums for both options and choose the larger valid even sum. Sorting dominates the runtime, giving O(n log n) time and O(1) extra space beyond the sort.
This approach works because parity is the only constraint preventing the maximum sum. By keeping the best candidates for odd-even swaps, you adjust the parity with the smallest possible loss in value.
Recommended for interviews: Interviewers expect the Greedy + Sorting solution. The brute force explanation shows you understand the constraint space, but recognizing that parity can be fixed with a minimal swap demonstrates strong reasoning with arrays, greedy algorithms, and sorting. The final solution runs in O(n log n) and handles all edge cases cleanly.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subsequence Enumeration | O(C(n,k) * k) | O(k) | Useful for understanding the constraint or verifying small inputs |
| Greedy + Sorting | O(n log n) | O(1) | General optimal solution; handles parity adjustments efficiently |