Максимальная четная сумма пары данного массива

Учитывая массив arr[] из N различных неотрицательных целых чисел, задача состоит в том, чтобы определить, существует ли четное число, которое может быть представлено как сумма двух различных элементов arr. Если он существует, верните максимальное такое число, иначе верните -1.

Примеры:

Input: N = 4, arr[] = {2, 3, 4, 5}
Output: 8
Explanation: The values that can be represented as the sum of two distinct elements of arr are 5, 6, 7, 8 and 9. 
We have two even number here, and the maximum is 8.

Input: N = 2, arr[] = {0, 3}
Output: -1
Explanation: The value represented as the sum of two distinct elements of arr is 1. 
We have no even number here, so -1 should be printed.

Наивный подход: основной подход:

Consider each pair sum by nested traversal and consider the maximum of all such pair sums that are even and present in the array.

Следуйте инструкциям, чтобы решить проблему:

• Инициализируйте результат как 0 при запуске.
• Пройдите массив, используя цикл от 0 до N - 2
  • Для каждого элемента рассмотрим сопряжение с каждым элементом в диапазоне от i + 1 до N – 1 и проверьте, является ли сумма пары четной или нечетной.
    • Если сумма четная, обновите результат, указав максимальную сумму пары на каждом шаге.
• Наконец, проверьте, равен ли результат 0, затем верните -1, иначе верните результат.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N ² )
Вспомогательное пространство: O(1)

Найдите максимальную сумму Pair, найдя максимальные четные и нечетные числа:

Для эффективного решения проблемы следуйте следующей идее:

The key point/ idea is that sum of any two even numbers or any two odd numbers is always even. Find two greatest even numbers and two greatest odd numbers, the final result will be the maximum sum of the two odd numbers and the sum of the two even numbers.

Следуйте инструкциям, чтобы решить проблему:

• Инициализируйте первое и второе максимальные нечетные и четные числа равными -1.
• Пройдите массив, чтобы найти первое максимальное четное и первое максимальное нечетное число.
• Пройдитесь по массиву еще раз, чтобы найти второе максимальное нечетное и второе максимальное четное число.
• Вычислить сумму пары максимум двух нечетных и пары максимум двух четных чисел и считать результат равным максимальному среди них.
• Если результат равен нулю, это означает, что не существует пары с четной суммой, поэтому верните -1, иначе верните максимальный результат.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)