合唱团问题：给定一组身高不同的人，删除其中几个人，使得剩下的人组成先升高后减少的合唱团队列
思路：正、反扫描
- left[i]表示正向第i个人为末尾的最长递增子序列
- right[i]表示反向第i个人为末尾的最长递增子序列
计算left[i]+right[i]-1便可找到最大的合唱团队列长度
题目描述
过山车在上坡下坡的过程是非常刺激的。如果把整个过山车的轨道当作是一个长度为n的数组num，那么在过山车上坡时数组中的值是呈现递增趋势的，到了最高点以后，数组中的值呈现递减的趋势，把符合这样先增后减规律的数组定义为金字塔数组，请你帮牛牛在整个num数组中找出长度最长的金字塔数组，如果金字塔数组不存在，请输出0。
示例1
输入
复制
4,[1,2,3,1]输出
复制
4
【思路】和合唱团类似，采取正、反向扫描
- left[i]表示从i位置向左组多可以连续递减多少次
- right[i]表示从i位置向右最多可以连续递减多少次
以left[]迭代计算为例：
- 若num[i]>num[i-1] 则left[i]=left[i-1]
- 否则,left[i]=0
峰顶法
最后，遍历那些山峰（left[i]>0 && right[i]>0）的left[i]+right[i]+1 找到其中的最大值
整个时间复杂度为线性级别： O(N)
int getMaxLength(int n, vector<int>& num) {// write code hereif(n==1)return 1;vector<int> left(n,0);//left[i]=k表示i位置向左可以下降多少元素vector<int> right(n,0);//right[i]=k表示i位置向右可以下降多少元素for(int i=1;i<n;i++)if(num[i]>num[i-1])left[i]=left[i-1]+1;for(int i=n-2;i>=0;i--)if(num[i]>num[i+1])right[i]=right[i+1]+1;int ans=0;for(int i=0;i<n;i++){if(left[i]>0 && right[i]>0)ans=max(ans,left[i]+right[i]+1);}return ans;}
另一种思路：峰谷法
寻找到那些峰谷（局部最低点 num[i]<num[i-1] && num[i]<num[i+1]）
两两峰谷之间的距离，即为中间波峰的长度