问题 ：三角形

(难度：中等) 竞技编程-提高思维

题目描述 有 n 根棍子，棍子 i 的长度为 $a\_i$。想要从中选出 3 根棍子组成一个三角形。请输出最大可能的三角形周长，如果无法组成三角形，则输出 0。

根据三角形的性质，任何三边的长度必须满足三角形不等式，即：

如果选出的 3 根棍子无法满足上述条件，则无法组成三角形。

输入格式

• 第一行，整数 n 表示棍子的数量。
• 第二行，长度为 n 的整数数组 $a={a1,a2,…,an}$ 表示每根棍子的长度。

输出格式

• 输出一个整数，表示最大周长的三角形的周长。如果无法组成三角形，输出 0。

示例 1 输入

5
3 4 5 6 7

输出

18

（例如，选择 5, 6, 7 组成三角形，周长为 18）

示例 2 输入

4
10 2 3 4

输出

9

（无法组成三角形，输出 0）

时间复杂度分析 由于需要选择 3 根棍子组成三角形，最简单的方法是枚举所有 3 根棍子的组合。最坏情况下需要枚举 $O(n^3)$ 次，这对于 $n≤100$ 是可以接受的。另一种优化方法是先将数组排序，然后通过遍历寻找符合三角形不等式的三根棍子，时间复杂度可以优化到 $O(n^2)$。