Sum of Three Numbers
Time limit1sMemory limit128 MB
Given up to 1000 distinct integers, find the largest set element expressible as a sum of three elements (repeats allowed).
- Level
Medium5 of 10
- Topics
- Two pointers, Sorting, Array
- Solved
- No attempts yet
Problem
Given a set U of N distinct positive integers, choose three numbers from U. The same element may be chosen more than once. If the sum of the three chosen numbers is also an element of U, that sum is a valid candidate. Find the largest valid candidate.
Input
The first line contains the positive integer N (5 <= N <= 1,000). Each of the next N lines contains one element of U. All given elements are distinct positive integers not greater than 200,000,000. The input is guaranteed to have at least one valid answer.
Output
Print the largest element d of U that can be written as x + y + z, where x, y, and z are elements of U. The same element may be used for more than one of x, y, and z.