Solution

Method 1 - Greedy + Parity Swap

Intuition

To maximize the sum, pick the k largest numbers. If their sum is even, return it. If odd, try to swap the smallest odd in the k largest with the largest even outside, or the smallest even in the k largest with the largest odd outside, to make the sum even. If not possible, return -1.

Approach

Sort nums in descending order.
Take the k largest numbers as the candidate subsequence.
If their sum is even, return it.
Otherwise, try to swap to make the sum even:
- Find the smallest odd in the k largest and the largest even outside.
- Find the smallest even in the k largest and the largest odd outside.
- If either swap is possible, return the maximum even sum after swap.
- Otherwise, return -1.

Code

[{"language":"C++","code":"#include <vector>\n#include <algorithm>\nusing namespace std;\nclass Solution {\npublic:\n    int largestEvenSum(vector<int>& nums, int k) {\n        sort(nums.rbegin(), nums.rend());\n        int n = nums.size();\n        int sum = 0;\n        int minOdd = 1e9+1, minEven = 1e9+1;\n        int maxOdd = -1, maxEven = -1;\n        for (int i = 0; i < k; ++i) {\n            sum += nums[i];\n            if (nums[i] % 2) minOdd = min(minOdd, nums[i]);\n            else minEven = min(minEven, nums[i]);\n        }\n        for (int i = k; i < n; ++i) {\n            if (nums[i] % 2) maxOdd = max(maxOdd, nums[i]);\n            else maxEven = max(maxEven, nums[i]);\n        }\n        if (sum % 2 == 0) return sum;\n        int ans = -1;\n        if (minOdd < 1e9+1 && maxEven != -1)\n            ans = max(ans, sum - minOdd + maxEven);\n        if (minEven < 1e9+1 && maxOdd != -1)\n            ans = max(ans, sum - minEven + maxOdd);\n        return ans;\n    }\n};\n// Leetcode signature: int largestEvenSum(vector<int>& nums, int k);","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;vector></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;algorithm></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">using</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> namespace</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> std</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-d

Related Tags