题解 | #合唱队#
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
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个数，那么每进来一个新的数，都要用二分查找法来得知要替换在哪个位置的数。
