Overview

This problem asks us to select \(2\) people from \(N\) members to maximize the sum of their ability values. It can be solved with a simple greedy approach: just select the \(2\) people with the highest ability values.

Analysis

Key Insight

Since we want to maximize the combined strength (the sum of the \(2\) people’s ability values), we can intuitively think “we should select \(2\) people with large ability values.”

Let’s verify that this is correct. If we denote the ability values of the \(2\) people as \(A_i\) and \(A_j\) (\(i \neq j\)), the combined strength is \(A_i + A_j\). To maximize this value: - First, make \(A_i\) as large as possible → select the person with the maximum ability value - Then, make \(A_j\) as large as possible → select the person with the second largest ability value

Therefore, selecting the top \(2\) people by ability value is optimal.

Naive Approach and Its Problems

We could also consider trying all possible pairs. Since there are \(\frac{N(N-1)}{2}\) ways to choose \(2\) people from \(N\), when \(N = 2 \times 10^5\), this requires approximately \(2 \times 10^{10}\) calculations, which would result in TLE (Time Limit Exceeded).

Solution

By sorting the array and extracting the top \(2\) elements, we can solve this in \(O(N \log N)\).

Algorithm

1. Sort the ability value array \(A\) in descending order (largest first)
2. The first \(2\) elements of the sorted array (\(A[0]\) and \(A[1]\)) are the top \(2\) people by ability value
3. Output \(A[0] + A[1]\)

Concrete Example

For \(N = 5\), \(A = [3, 1, 4, 1, 5]\): - Sort in descending order: \(A = [5, 4, 3, 1, 1]\) - Ability values of the top \(2\) people: \(5\) and \(4\) - Maximum combined strength: \(5 + 4 = 9\)

Complexity

• Time complexity: \(O(N \log N)\)
  • \(O(N \log N)\) for sorting, \(O(1)\) for retrieving the top \(2\) elements
• Space complexity: \(O(N)\)
  • Space needed to store the array \(A\)

Implementation Notes

• In Python, you can sort in descending order using sort(reverse=True)

• You can also achieve the same result by sorting in ascending order and taking the last \(2\) elements (\(A[N-2]\) and \(A[N-1]\))

• Since the maximum ability value is \(10^9\), the sum of \(2\) people can be at most \(2 \times 10^9\), but in Python you don’t need to worry about integer overflow

  Source Code

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
print(A[0] + A[1])

---

This editorial was generated by claude4.5opus.