2098. Subsequence of Size K With the Largest Even Sum 🔒

Description

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

Solutions

Solution 1: Greedy + Sorting

We notice that the problem involves selecting a subsequence, so we can consider sorting the array first.

Next, we greedily select the largest \(k\) numbers. If the sum of these numbers is even, we directly return this sum \(ans\).

Otherwise, we have two greedy strategies:

1. Among the largest \(k\) numbers, find the smallest even number \(mi1\), and then among the remaining \(n - k\) numbers, find the largest odd number \(mx1\). Replace \(mi1\) with \(mx1\). If such a replacement exists, then the sum after replacement \(ans - mi1 + mx1\) is guaranteed to be even;
2. Among the largest \(k\) numbers, find the smallest odd number \(mi2\), and then among the remaining \(n - k\) numbers, find the largest even number \(mx2\). Replace \(mi2\) with \(mx2\). If such a replacement exists, then the sum after replacement \(ans - mi2 + mx2\) is guaranteed to be even.

We take the largest even sum as the answer. If no even sum exists, return \(-1\).

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of the array.

Python3JavaC++GoTypeScript

class Solution:
    def largestEvenSum(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = sum(nums[-k:])
        if ans % 2 == 0:
            return ans
        n = len(nums)
        mx1 = mx2 = -inf
        for x in nums[: n - k]:
            if x & 1:
                mx1 = x
            else:
                mx2 = x
        mi1 = mi2 = inf
        for x in nums[-k:][::-1]:
            if x & 1:
                mi2 = x
            else:
                mi1 = x
        ans = max(ans - mi1 + mx1, ans - mi2 + mx2, -1)
        return -1 if ans < 0 else ans

class Solution {
    public long largestEvenSum(int[] nums, int k) {
        Arrays.sort(nums);
        long ans = 0;
        int n = nums.length;
        for (int i = 0; i < k; ++i) {
            ans += nums[n - i - 1];
        }
        if (ans % 2 == 0) {
            return ans;
        }
        final int inf = 1 << 29;
        int mx1 = -inf, mx2 = -inf;
        for (int i = 0; i < n - k; ++i) {
            if (nums[i] % 2 == 1) {
                mx1 = nums[i];
            } else {
                mx2 = nums[i];
            }
        }
        int mi1 = inf, mi2 = inf;
        for (int i = n - 1; i >= n - k; --i) {
            if (nums[i] % 2 == 1) {
                mi2 = nums[i];
            } else {
                mi1 = nums[i];
            }
        }
        ans = Math.max(ans - mi1 + mx1, ans - mi2 + mx2);
        return ans < 0 ? -1 : ans;
    }
}

class Solution {
public:
    long long largestEvenSum(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long long ans = 0;
        int n = nums.size();
        for (int i = 0; i < k; ++i) {
            ans += nums[n - i - 1];
        }
        if (ans % 2 == 0) {
            return ans;
        }
        const int inf = 1 << 29;
        int mx1 = -inf, mx2 = -inf;
        for (int i = 0; i < n - k; ++i) {
            if (nums[i] % 2) {
                mx1 = nums[i];
            } else {
                mx2 = nums[i];
            }
        }
        int mi1 = inf, mi2 = inf;
        for (int i = n - 1; i >= n - k; --i) {
            if (nums[i] % 2) {
                mi2 = nums[i];
            } else {
                mi1 = nums[i];
            }
        }
        ans = max(ans - mi1 + mx1, ans - mi2 + mx2);
        return ans < 0 ? -1 : ans;
    }
};

func largestEvenSum(nums []int, k int) int64 {
    sort.Ints(nums)
    ans := 0
    n := len(nums)
    for i := 0; i < k; i++ {
        ans += nums[n-1-i]
    }
    if ans%2 == 0 {
        return int64(ans)
    }
    const inf = 1 << 29
    mx1, mx2 := -inf, -inf
    for _, x := range nums[:n-k] {
        if x%2 == 1 {
            mx1 = x
        } else {
            mx2 = x
        }
    }
    mi1, mi2 := inf, inf
    for i := n - 1; i >= n-k; i-- {
        if nums[i]%2 == 1 {
            mi2 = nums[i]
        } else {
            mi1 = nums[i]
        }
    }
    ans = max(-1, max(ans-mi1+mx1, ans-mi2+mx2))
    if ans%2 < 0 {
        return -1
    }
    return int64(ans)
}

function largestEvenSum(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let ans = 0;
    const n = nums.length;
    for (let i = 0; i < k; ++i) {
        ans += nums[n - i - 1];
    }
    if (ans % 2 === 0) {
        return ans;
    }
    const inf = 1 << 29;
    let mx1 = -inf,
        mx2 = -inf;
    for (let i = 0; i < n - k; ++i) {
        if (nums[i] % 2 === 1) {
            mx1 = nums[i];
        } else {
            mx2 = nums[i];
        }
    }
    let mi1 = inf,
        mi2 = inf;
    for (let i = n - 1; i >= n - k; --i) {
        if (nums[i] % 2 === 1) {
            mi2 = nums[i];
        } else {
            mi1 = nums[i];
        }
    }
    ans = Math.max(ans - mi1 + mx1, ans - mi2 + mx2);
    return ans < 0 ? -1 : ans;
}

Comments