The sum of two elements is even if the elements are both even or both odd.

We try the both cases.

Consider the problem of maximizing two even numbers you choose. We first rule out the case that there is only one even number. Then we consider the case where it has two or more even numbers.

When the even numbers in \(A\) are sorted in desceding order, the sum is maximized when adding the first and second values. Therefore, by sorting the values, we can answer the problem in a total of \(O(N\log N)\) time. (Same applies for odd numbers.)

Sample code (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;
}