有\(n\)根棍子，棍子\(i\)的长度为\(a_i\)。想要从中选出3根棍子组成周长尽可能长的三角形。请输出最大周长的三根棍子，若无法组成三角形则输出空字符串。
限制条件
\(3\le n\le 100\)
\(1\le a_i\le 10^6\)
例如，输入：
2,3,4,5,10
输出：
3,4,5
输入：
4,5,10,20
输出：
[空行]
众所周知，满足三角形的条件为任意两边之和大于第三边，略微一想，等价于两短边之和大于最长边。知道这个条件后，立刻有了穷举的思路，利用三重循环，遍历所有可能的三元组，然后判断满足此条件的三元组周长是否大于已经发现的最大三元组周长，如果是，那么替换，否则继续找。寻找三元组有\(C^3_n\)种可能性，这是\(O(n^3)\)的算法。具体的实现可以参考这里解法一。
实际上，由于题目限制了说\(n\)的范围仅在3到100之间，所以3次方也并没有多少计算，所以这样的解法也可行。
不过对于\(n\)很大的情况，三次方的算法会有很多的冗余计算，常常较慢。这个问题是否有更快的解决办法。我们可以进一步形式化。假设选出的三条边为\(a_i\),\(a_j\),\(a_k\)，构成三角形的条件为
\(a_i\le a_j\le a_k\)
\(2a_k<a_i+a_j+a_k\le 3a_k\)
当\(a_i\le a_j\le a_k\)时，\(a_i+a_j+a_k\le 3a_k\)是显然成立的，\(2a_k<a_i+a_j+a_k\)才是三角形成立的重要条件，变形移项后发现\(a_i>a_k-a_j\)。在充分考虑大小关系和移项后的不等式之后，很快会有第二种思路：先对\(n\)根棍子按长度从小到大排序，从大到小循环\(a_k\)和\(a_j\)，然后只要\(a_{j-1}>a_k-a_j\)，那么就找到了一个合理的三角形。为什么只要找\(a_{j-1}\)就可以呢，因为排序后，如果\(a_{j-1}\)都小于等于\(a_k-a_j\)，那么更前面的数字就更不用看了。这个解法只对\(j\)和\(k\)做了循环，所以复杂度为\(O(n^2)\)。具体的实现可以参考这里解法二。
实测在\(n\)为200多时，解法一需要\(1s\)以上的时间，而解法二只需要几个毫秒。
继续思考，还能更高效吗。前面形式化的时候，提到说\(a_i+a_j+a_k\le 3a_k\)是显然成立的。不过即使是显然成立的条件，也依旧能够作为剪枝的条件，何况还是个上确界。在第二种思路的基础上，如果继续向下看的\(a_k\)都发现\(3a_k\)已经小于等于当前找到的最大的周长，那么其余的部分就没有看的的必要了。这有种贪心的意味在其中。这个剪枝可以让算法的效率比几个毫秒还更快。具体的实现参考这里解法三。
实际上在想出解法二，论证为什么只要看\(a_{j-1}>a_k-a_j\)就可以的时候，我们就会产生一个猜想，最终的答案一定是排序后下标连续的三个数。对于\(a_k\)，周长的范围是大于\(2a_k\)，小于等于\(3a_k\)。由于\(i<j<k\)，那么必然满足小于等于\(3a_k\)的条件。对于下界，如果\(a_{k-2}+a_{k-1}\)都不能够大于\(a_k\)，那么也就不存在其它的\(i\)和\(j\)能满足大于\(a_k\)的条件了。所以只需要检查\(a_{k-2}+a_{k-1}>a_{k}\)即可。这样，只需要贪心地从最大的数字开始遍历就可以，最坏情况下是\(O(n)\)的复杂度。由此整个问题的瓶颈就转移给了排序。如果用基数或者计数排序，整个算法的复杂度就是\(O(n)\)了。具体的实现参考这里解法四。
