Welcome to Subscribe On Youtube

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

  • 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(-1, Math.max(ans - mi1 + mx1, ans - mi2 + mx2));
            return ans % 2 != 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 % 2 || ans < 0 ? -1 : ans;
        }
    };
    
  • 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 % 2 else 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;
    }
    
    

All Problems

All Solutions