整数のリストが与えられ、そのうちのいくつかは負であるかもしれません。

Question

O（n2）のそばには解決策がありますか？ 私はすべての値をループすることを考えていましたが、合計を取得しました

Answer 1

2つの最大要素からなるペアが最大の数になります。わずか2つの、最大の要素を検索し、それらを合計 - それは、最大数の合計、あなたはK最大の要素を見つけるためにselection algorithmを使用することができ、一般的なk要素についてはO(n)

あり、その後、第二の繰り返しで - すべての要素が大きいの和それから。

Answer 2

2つの最大値を取得する場合は、ループを1つだけ必要とするため、アルゴリズムをO(n)にしないとO(n^2)になります。

より複雑なペア解析が必要な場合は、整数でクイックソートを実行すると、最も大きなペアとなる最大の2つの番号と希望する他のペアの組み合わせを選択できます。