题解 | #合唱队#
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
# 2024年10月30日 周三 上午7:45
def f(nums):
dp = [1] * (N) # 注意dp是定义在函数内部的，而且长度为N,初始值为1，因为每个人自己就能组成一个子序列，长度为1，所以dp的初始值为1
for i in range(len(nums)):
for j in range(i + 1):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1) # 注意这里求的是max，因为dp表示的是最长子序列长度，所以要求max
return dp
N = int(input())
nums = list(map(int, input().split()))
L1 = f(nums)
L2 = f(nums[::-1])[::-1]
#print(L1)
#print(L2)
ls = []
for i in range(len(nums)):
ls.append(L1[i] + L2[i])
#print(ls)
m = max(ls) - 1
print(N - m)
投递美团等公司9个岗位
查看11道真题和解析