题解 | #合唱队#

import bisect

def inc_max(s):
    q = []
    dp=[]
    for n in s:
        idx = bisect.bisect_left(q, n)
        dp.append(idx+1)
        if idx == len(q):
            q.append(n)
        else:
            q[idx] = n
    return dp


N = int(input())
s = list(map(int, input().split()))
left_s = inc_max(s)  # 从左至右
right_s = inc_max(s[::-1])[::-1]  # 从右至左
sum_s = [left_s[i] + right_s[i] - 1 for i in range(len(s))]  # 相加并减去重复计算
print(str(N - max(sum_s)))

这个更简单一点

新建一个数组，然后第一个数先放进去，然后第二个数和第一个数比较，如果说大于第一个数，那么就接在他后面，如果小于第一个数，那么就替换，一般的，如果有i个数，那么每进来一个新的数，都要用二分查找法来得知要替换在哪个位置的数。