用c++做为了在即将到来的晚会上有更好的演出效果作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 nn 个人第 ii 个人的身高为 h_ih i 米1000 le h_i le 20001000≤h i ≤2000并已知任何两个人的身高都不同。假定最终排出的队形是 AA 个人站成一排为了简化问题小 A 想出了如下排队的方式：他让所有的人先按任

算法思路：

• 题目中的插入操作可以看做是不断地将一个数插入一个已经排好序的序列中，可以想到使用插入排序的思想。
• 我们从左到右遍历初始队形，对于每个人，我们需要找到最长的递增子序列和最长的递减子序列，然后将这个人插入到这两个子序列中的一个，使得插入后这两个子序列的长度之和最大（因为这样可以保证插入的次数最少）。
• 插入的时候，如果插入到递增子序列中，则从后往前找到第一个比它小的数，插入到这个数的后面；如果插入到递减子序列中，则从后往前找到第一个比它大的数，插入到这个数的前面。

C++ 代码