A kite workshop keeps a bin of rigid wooden spars of various lengths. To build a triangular kite frame, the crafters select exactly three spars and join their ends together into a closed triangle — a shape that is only physically achievable when the sum of the two shorter selected lengths is strictly greater than the longest selected length. Among every way of choosing three spars from the bin that can be joined into a valid triangle, the workshop wants the largest possible total perimeter (the sum of the three chosen lengths). If no three spars in the bin can form a valid triangle, report that no frame can be built.
Line 1: a single integer n, the number of spars in the bin. Line 2: n space-separated integers, the lengths of the spars.
Print a single integer: the maximum perimeter of any triangular frame that can be built from three of the spars, or 0 if no three spars can form a valid triangle.
Example 1
Input
3 2 1 2
Expected
5
Explanation
The only way to choose three spars is (2, 1, 2). Since 1 + 2 = 3 > 2, these lengths satisfy the triangle inequality, so they form a valid triangle with perimeter 2 + 1 + 2 = 5.
Example 2
Input
4 1 2 1 10
Expected
0
Explanation
Every triple of spars drawn from (1, 2, 1, 10) includes the length-10 spar, and no two of the remaining lengths (1, 2, and 1) sum to more than 10, so no triple satisfies the triangle inequality. No frame can be built, so the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →