Overview

Given the ability values \(A_i\) of \(N\) people, select \(2\) different people such that the sum of their ability values (total strength) is maximized.

Analysis

Since total strength is “the sum of two people’s ability values,” the optimal strategy to maximize it is to select the 1st and 2nd highest ability values.
This is because, for any pair, one person cannot exceed the maximum value, and the other cannot exceed the second maximum value. Therefore, the sum of the top two values is the upper bound, and this upper bound is achievable.

If we naively try all pairs, the number of pairs is \(\binom{N}{2} = O(N^2)\).
Since \(N \le 2 \times 10^5\), \(N^2\) can be up to approximately \(4 \times 10^{10}\), so brute force will not finish in time (TLE).

The solution is to scan the array once and only track the maximum value and the second maximum value. This allows us to find the answer in \(O(N)\) overall.

Example: \(A = [3, 10, 7, 10]\)
The maximum is \(10\), and the second maximum is also \(10\), so the answer is \(20\).

Algorithm

1. Initialize variables max1 (maximum value) and max2 (second maximum value) to sufficiently small values.
2. Iterate through the array from left to right, and for each element \(x\):
   • If \(x > \text{max1}\), update max2 = max1 and max1 = x
     (Since the maximum is being updated, the previous maximum drops to 2nd place)
   • Otherwise, if \(x > \text{max2}\), update max2 = x
3. Output max1 + max2 at the end.

This process always maintains “the top 2 values seen so far.”

Complexity

• Time complexity: \(O(N)\) (only a single scan)
• Space complexity: \(O(1)\) (only storing two maximum values)

Implementation Notes

• The condition that the same member cannot be selected twice is naturally satisfied by “managing the top two values separately” (the same element is not double-counted).

• When updating max1, it is important to always move max1 to max2 first. Forgetting this will corrupt the second maximum value.

• Since the input can be large, using fast input methods like sys.stdin.buffer.read() is recommended to be safe.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:1+n]

    max1 = -1
    max2 = -1
    for x in a:
        if x > max1:
            max2 = max1
            max1 = x
        elif x > max2:
            max2 = x

    print(max1 + max2)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.