# 2098. Subsequence of Size K With the Largest Even Sum
###### tags: `Leetcode` `Medium` `Two Pointers`
Link: https://leetcode.com/problems/subsequence-of-size-k-with-the-largest-even-sum/
## 思路
### 思路一 $O(NlogN)$ $O(N)$
将$nums$分成奇数组和偶数组，各自从大到小排序。显然，如果奇数取$0$个，那么偶数就取前$k$个；如果奇数取前$1$个，那么偶数就取前$k-1$个...于是只要两个指针$(i,j)$，$i$在奇数组从前往后移动，$j$在偶数组从后往前移动，用$k$次找出最大的$presum1+presum2$.

需要注意的有两点。首先，不是每一种(i,j)组合得到的presum1+presum2都是偶数，我们肯定会舍弃掉不合条件的组合。
### 思路二 $O(NlogN)$ $O(1)$
参考[这里](https://leetcode.com/problems/subsequence-of-size-k-with-the-largest-even-sum/discuss/1620312/Sum-k-largest-numbers-O(n))
先针对所有数字排序，取k个最大的，如果sum为偶数 done
否则找到前k个里面最小的一个奇数和一个偶数（因为要替换的一定是他们）
然后遍历除了前k个之前的所有数字 看是否能补齐k个数
（之前自己想要找到前k个里面最小的一个奇数和一个偶数，和后边的数字里面最大的一个奇数和一个偶数 要分情况讨论有点麻烦）
## Code
### 思路一

class Solution {
    public long largestEvenSum(int[] nums, int k) {
        List<Integer> even = new ArrayList<>();
        List<Integer> odd = new ArrayList<>();
        for(int num:nums){
            if(num%2==0) even.add(num);
            else odd.add(num);
        }
        Collections.sort(even, Collections.reverseOrder());
        Collections.sort(odd, Collections.reverseOrder());
        
        long sum = -1;
        long[] sum1 = new long[even.size()+1], sum2 = new long[odd.size()+1];
        for(int i = 0;i < even.size();i++){
            sum1[i+1] = even.get(i) + sum1[i];
        }
        for(int i = 0;i < odd.size();i++){
            sum2[i+1] = odd.get(i) + sum2[i];
        }
        
        int p1 = Math.min(k, even.size());
        int p2 = k-p1;
        
        while(p1>=0 && p2<sum2.length){
            if((sum1[p1]+sum2[p2]) %2==0){
                sum = Math.max(sum1[p1]+sum2[p2], sum);
            }
            p1--;
            p2++;
        }
        return sum;
    }
}

### 思路二
java

class Solution {
    public long largestEvenSum(int[] nums, int k) {
        Arrays.sort(nums);
        long sum = 0;
        for(int i=0; i<k; i++){
            sum += nums[nums.length-1-i];
        }
        if(sum%2==0) return sum;
        int[] min_k = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
        long ans = -1;
        for(int i=0; i<k; i++){
            min_k[nums[nums.length-1-i] % 2] = Math.min(min_k[nums[nums.length-1-i] % 2], nums[nums.length-1-i]);
        }
        for(int i=k; i<nums.length; i++){
            ans = Math.max(ans, sum-min_k[1-(nums[nums.length-1-i]%2)]+nums[nums.length-1-i]);
        }
        return ans;
    }
}

c++

class Solution {
public:
    long long largestEvenSum(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long long sum = 0;
        int n = nums.size();
        for(int i=0; i<k; i++){
            sum += nums[n-1-i];
        }
        if(sum%2==0) return sum;
        long long ans = -1;
        int min[2];
        for(int i=n-1; i>=n-k; i--){
            min[nums[i]%2] = nums[i];
        }
        for(int i=n-k-1; i>=0; i--){
            ans = max(ans, nums[i]+sum-min[1-nums[i]%2]);
        }
        return ans;
    }
};