合唱队形问题：N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使剩下的K位同学不改变顺序排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K，他们的身高分别为T1,T2,…,TK，则他们的身高满足T1<T2<…< Ti-1<Ti>Ti+1>…>TK，其中1≤i≤K。已知所有N位同学的身高，计算最少需要几位同学出列，可以使剩下的同学排成合唱队形？（提示：用动态规划找最长上升子序列和最长下降子序列）
样例输入：
8
186 186 150 200 160 130 197 220
样例输出：
4
分析：找出以L[i]结尾的最长上升子序列的长度L1[i] 以及以L[i]开始的最长下降子序列的长度L2[i]，找出L1[i]+L2[i]的最大值，就是排队人数的最大值num，出队的人数就是总人数-num
def longest_sequences(L):L1=[1]*len(L)#L1[i]存放以L[i]结尾的最长上升子序列的长度L2=[1]*len(L)#L2[i]存放以L[i]开始的最长下降子序列的长度for i in range(1,len(L)):#求最长上升子序列X=[]for j in range(0,i):if L[j]<L[i]:X.append(j)for x in X:if L1[i]<L1[x]+1:L1[i]=L1[x]+1#print(L1)for i in range(len(L)-1,-1,-1):#求以L[i]开始的最长下降子序列,从后往前求，注意下标X=[]for j in range(i,len(L)):if L[j]<L[i]:X.append(j)for x in X:if L2[i]<L2[x]+1:L2[i]=L2[x]+1#print(L2)Max2=0for i in range(0,len(L)):#求L[i]左边序列和右边序列之和的最大值if L1[i]+L2[i]>Max2:Max2=L1[i]+L2[i]return Max2-1 #i在序列中算了两遍，要减去1while True:n=int(input("请输入学生个数："))s=input("请依次输入每个学生的身高，用空格隔开：")L=[int(e) for e in s.split(" ")]num=longest_sequences(L)print(num)print("最少需要抽出",len(L)-num,"人")