\(2\) 要素の和が偶数になるのは、偶数と偶数を足したときか奇数と奇数を足したときです。

それぞれの場合を試します。

偶数を \(2\) 個選び、和を最大化する問題を考えます。 まず、偶数が \(1\) 個しか存在しない場合を場合分けで処理します。以下、偶数が \(2\) 個以上存在する場合のみを考えます。

\(A\) に含まれる偶数を降順に並び替えると、和が最大になるのは先頭の値と \(2\) 番目の値を足したときです。よってソートを行うことでこの問題に \(O(N\log N)\) で答えることができました。（奇数の場合も同様です。）

実装例(c++):

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> odd, even;
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if(a & 1)
            odd.push_back(a);
        else
            even.push_back(a);
    }
    sort(odd.rbegin(), odd.rend());
    sort(even.rbegin(), even.rend());
    int mx = -1;
    if(odd.size() >= 2) mx = max(mx, odd[0] + odd[1]);
    if(even.size() >= 2) mx = max(mx, even[0] + even[1]);
    cout << mx << endl;
}