Overview

Given \(N\) members, select \(2\) distinct members to maximize the sum of their ability values (overall strength).

Analysis

The goal of this problem is to find the maximum value of \(A_i + A_j\) when choosing distinct indices \(i, j\) from the array \(A\).

Key Insight

To maximize the sum, we can see that we should pair “the member with the highest ability value among all members” with “the member with the second highest ability value”. For example, if the ability values are \([3, 8, 5, 1, 8]\), the maximum is \(16\), obtained by adding the maximum value \(8\) and the next largest value \(8\) (or \(5\)).

Why a Naive Approach Won’t Work

Consider the approach of checking all pairs (nested loops). In this case, the number of pairs is \(\frac{N(N-1)}{2}\). Substituting the constraint \(N = 2 \times 10^5\), this requires approximately \(2 \times 10^{10}\) computations. Under typical competitive programming time limits (around 2 seconds), the number of operations that can be performed per second is roughly \(10^8\), so this approach would result in “Time Limit Exceeded (TLE)”.

Therefore, we need to efficiently find the largest and second largest values without examining all pairs.

Algorithm

The simplest approach is to sort the array.

1. Sort the given \(N\) ability values in descending order (from largest to smallest).
2. Take the first \(2\) elements (\(A_0\) and \(A_1\)) of the sorted array.
3. Output their sum.

Sorting algorithms are very fast, so this easily fits within the time constraints.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting \(N\) elements takes \(O(N \log N)\) time. When \(N = 2 \times 10^5\), \(N \log N\) is approximately \(3.6 \times 10^6\), which can be computed well within the time limit.
• Space Complexity: \(O(N)\)
  • Memory is needed to store the ability values of \(N\) members in a list.

Implementation Notes

• Reading large input: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() or similar methods.

• Sort order: Using a.sort(reverse=True) sorts the array in descending order. If you sort in ascending order (smallest to largest), you can reference the last two elements (a[-1] and a[-2]).

  Source Code

import sys

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    a = list(map(int, input_data[1:]))
    
    # 能力値を降順（大きい順）にソート
    a.sort(reverse=True)
    
    # 上位2人の能力値の和が最大値となる
    max_total_power = a[0] + a[1]
    
    # 結果を出力
    print(max_total_power)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.