概要

\(N\) 人の能力値 \(A_i\) から異なる \(2\) 人を選び、能力値の和（総合力）が最大となる値を求めます。

考察

総合力は「2 人の能力値の和」なので、最大の総合力を作るには 能力値が大きい順に 1 位と 2 位を選ぶのが最適です。
なぜなら、どんなペアでも片方は「最大値」以上にはできず、もう片方も「2 番目の最大値」以上にはできないため、上位 2 つの合計が上限になり、それが実現できます。

素朴に全ペアを試すと、ペア数は \(\binom{N}{2} = O(N^2)\) 個あります。
\(N \le 2 \times 10^5\) なので、\(N^2\) は最大で約 \(4 \times 10^{10}\) となり、全探索は時間内に終わりません（TLE）。

解決策は、配列を一度走査して 最大値と 2 番目の最大値だけを管理することです。これなら全体で \(O(N)\) で求められます。

例：\(A = [3, 10, 7, 10]\)
最大値 \(10\)、2 番目の最大値も \(10\) なので答えは \(20\)。

アルゴリズム

1. 変数 max1（最大値）、max2（2 番目の最大値）を十分小さい値で初期化する。
2. 配列を左から順に見ていき、各要素 \(x\) について：
   • もし \(x > \text{max1}\) なら、max2 = max1、max1 = x と更新する
     （最大値が更新されるので、以前の最大値が 2 位に落ちる）
   • そうでなく、もし \(x > \text{max2}\) なら、max2 = x と更新する
3. 最後に max1 + max2 を出力する。

この処理で常に「ここまででの上位 2 つ」が保たれます。

計算量

• 時間計算量: \(O(N)\)（1 回の走査のみ）
• 空間計算量: \(O(1)\)（最大値 2 つを保持するだけ）

実装のポイント

• 同じメンバーを 2 回選べない条件は、「上位 2 つの値を別々に管理する」ことで自然に満たせます（同じ要素を二重に数えない）。

• max1 更新時に 必ず max2 を先に max1 に移すのが重要です。これを忘れると 2 番目の最大値が壊れます。

• 入力が大きいので、sys.stdin.buffer.read() のような高速入力を使うと安全です。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。