Python题解 | #合唱队#
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
import bisect
import sys
def f(n, lis):
dp = [1] * n
arr = [lis[0]]
for i in range(1, n):
if lis[i] > arr[-1]:
arr.append(lis[i])
dp[i] = len(arr)
else:
pos = bisect.bisect_left(arr, lis[i])
arr[pos] = lis[i]
dp[i] = pos + 1
return dp
while True:
try:
a = int(input())
list1 = list(map(int, input().split()))
left_s = f(n=a, lis=list1)
right_s = f(a, list1[::-1])[::-1]
sum_s = [0] * a
for i in range(a):
sum_s[i] = left_s[i] + right_s[i] - 1
print(a - max(sum_s))
except:
break
投递美团等公司10个岗位