题目描述
计算最少出列多少位同学，使得剩下的同学排成合唱队形

说明：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<ti>Ti+1>......>TK。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。</ti>

请注意处理多组输入输出！

思路：

  1. 对于题目，所有人都已经站好位，不能再改变位置了，只能从当中去掉人组成合唱队。同时，可以考虑中间的人两边没有人的情况（比如两头的两个人，或者这个人太矮周围的人都比他高的情况），但是这种情况基本被pass掉。
  2. 计算出每个人左边能出现的最多的人数：
    比如题中所给出的示例：186 186 150 200 160 130 197 200。首先如果第一个数186在中间，左边没有数，就自己一个人，所以是1；第二个数186因为左边那个人跟他一边高，没有比他矮的了，所以也是1；第三个数150，左边的人都比他高，他如果是中间的话左边也他自己一个人，所以还是1；第四个数200，因为不能换位置，所以只能留186或者150，加上自己，就是2...最后再以197为例，左边保留150,160是左边人最多的情况，再加上自己，就是3。所以每个人左边人最多的情况（加上自己）就是（186）1 1 1 2 2 1 3 4（200）。同理，看一下每个人右边可能出现最多的人，这时我们从后往前看。200在最右面，所以自己一个人，是1；197最右面没有比他矮的，自己，是1...160左边一个比他矮的，所以算上自己是2，以此类推。所以每个人右边人做多的情况（加上自己）就是（186）3 3 2 3 2 1 1 1（200）
  3. 所以将上面两个划横线的对应相加，就可以得到自己如果是中间的那个人，可以得到的最大的合唱队人数。当然，自己加了两遍，所以得减掉一个自己。另外题目问的是最少去掉的人，所以最后的结果：
    总人数 - 该数所在队列人数 = 需要出队的人数
    代码1：
    dp的顺序查找，时间复杂度O(N^2)
    def left_max(l):
 # 计算每个人左边出现的最多的人数
 # 186 186 150 200 160 130 197 200
 dp = [1] * len(l) # 若左边没有比自己小的数，则为自己本身，所以初始值为1
 for i in range(len(l)): # 从左往右遍历
     for j in range(i):
         if l[j]<l[i] and dp[i]<dp[j]+1:
             dp[i] = dp[j]+1
       # if l[j]<l[i]:
       #     dp[i] = max(dp[i],dp[j]+1) 会超时
 return dp #1 1 1 2 2 1 3 4
           # 从右往左推每个人右边可以站的最多的人数
           # 3 3 2 3 2 1 1 1
while True:
 try:
     N = int(input())
     ss = list(map(int,input().split()))
     left_s = left_max(ss)
     right_s = left_max(ss[::-1])[::-1]
     sum_s = []
     for i in range(len(left_s)):
         # left_s[i]+right_s[i]-1表示此人是中间位置的人时，合唱队的人数
         sum_s.append(left_s[i]+right_s[i]-1)
     print(str(N-max(sum_s)))
 except:
     break
    代码2：
    二分查找，时间复杂度0(logN)
    import bisect
def max_l(l,dp):
 dp += [1] # dp[i]表示第i个人左边能够站的最多的人数
 b = [float('inf') for i in range(len(l))] # 往b列表中插入，则初始化应该为无穷大
 b[0] = l[0] # 第一个人
 for i in range(1,len(l)):
     # print(b,l[i])
     pos = bisect.bisect_left(b,l[i])
     # 在 b 中找到 l[i] 合适的插入点以维持有序。
     # print(pos)
     b[pos] = l[i]
     dp += [pos+1]
 return dp
while True:
...