题解：合唱队（最长递增子序列改进）

一、描述

二、分析及解答 分析

第一步： 分别求从第一个同学位置 T 0 T_{0} T0​开始到当前同学位置 T i T_{i} Ti​，可以达成最长递增子序列的同学数为 n i l e f t n_{i}^{left} nileft​；从当前同学位置 T i T_{i} Ti​到最后一个同学位置 T N − 1 T_{N-1} TN−1​，可以达成最长递减子序列的同学数为 n i r i g h t n_{i}^{right} niright​（可以对之后的数列取逆序，然后按求最长递增子序列来求，对结果再取逆序）。
第二步： 从左到右依次以当前同学 T i T_{i} Ti​为中心，身高向两边递减，求最少出列的同学个数。为 N − ( n i l e f t + n i r i g h t − 1 ) N-(n_{i}^{left}+n_{i}^{right}-1) N−(nileft​+niright​−1)，保存最少的值即可。
核心算法： 最长递增子序列。
算法思想： 动态规划，二分法。

2.1 动态规划（ O ( N 2 ) O(N^2) O(N2)）

def get_LIS(highs):
    n = len(highs)
    count = [1]*n
    for i in range(1,n):
        for j in range(i):
            if highs[j] < highs[i]:
                count[i] = max(count[i],count[j]+1)
    return count
n = input()
n = int(n)
highs = []
highs = input()
highs = [int(high) for high in highs.split()]
ascend_count = get_LIS(highs)
descend_count = get_LIS(highs[::-1])[::-1]
# print(ascend_count)
# print(descend_count)
print(n-max(ascend_count[i] + descend_count[i] - 1 for i in range(n)))

2.2 二分法（ O ( N l o g ( N ) ) O(Nlog(N)) O(Nlog(N))）

def get_LIS_bi(highs):
    n = len(highs)
    dp = []
    dp.append(highs[0])
    count = [1]*n
    for i in range(1,n):
        cur = highs[i]
        if cur > dp[-1]:
            dp.append(cur)
            count[i] = len(dp)
        else:
            left,right = 0,len(dp)-1
            while(left<=right):
                mid = (left+right)//2
                if dp[mid] < cur:
                    left = mid + 1
                else:
                    right = mid - 1
            dp[left]=cur
            count[i] = left+1
        
    return count
n = input()
n = int(n)
highs = []
highs = input()
highs = [int(high) for high in highs.split()]
ascend_count = get_LIS(highs)
descend_count = get_LIS(highs[::-1])[::-1]
# print(ascend_count)
# print(descend_count)
print(n-max(ascend_count[i] + descend_count[i] - 1 for i in range(n)))

如有问题或建议欢迎私信。
严禁私自转载，侵权必究。

参考：
[1] 最长上升子序列 (LIS) 详解+例题模板 (全) [CSDN]
[2] 二分查找之第一个大于小于等于 target 的值 [CSDN]
[3] 题解 | #合唱队# [牛客网]