[interesting question] find an element which is sum of two other elements

--------------------------------------------------------------------------------

Hello everyone,


I am discussing with my friends about an interesting question about find the maximum element in a set, which is the sum of two other elements.

For example, in set {1, 2, 3, 5, 8, 10}, the answer is 10 (10 = 8 + 2),
which is the maximum element we can find, and it is the sum of two
other elements (8 and 2) in the set.

Currently, I only have brute-force solution. Sorting the set, which takes O(nlgn) time, then enumerate them one by one to find whether two elements can sum up to the maximum element (if the most maximum element does not meet the condition, move to the second largest one), which takes O(n^2) time, so the total time complexity is O(n^2).

I am wondering whether any one have better ideas?


thanks in advance,
George