一、题目

二、示例

三、代码

import bisect
def fun(N, s):
    temp = [s[0]]
    dp = [1] * N
    for i in range(1, N):
        if s[i] > temp[-1]:
            temp.append(s[i])
            dp[i] = len(temp)
        else:
            item = bisect.bisect_left(temp, s[i])
            temp[item] = s[i]
            dp[i] = item + 1
    return dp

while True:
    try:
        N = int(input())
        nums = list(map(int, input().split()))
        res = []
        left = fun(N,nums)
        right = fun(N, nums[::-1])[::-1]
        res = [left[i]+right[i]-1 for i in range(N)]
        print(N - max(res))
    except:
        break

四、算法说明

• 题目的含义可以转化为，求寻找最长的子序列；
• 定义子函数fun(N, s)寻找列表s中元素的最长子序列：
  • 遍历列表元素，用temp存储遍历过的元素，如果当前列表元素大于temp[-1]，说明升序子序列继续延长，更新子序列长度dp[i]；
  • 否则，找到当前元素在temp中的二分位置item（也就是可以按大小顺序插入的位置），将其替换temp[item] = s[i]，这样保证temp是顺序排列的子序列，然后更新当前元素的子序列长度dp[i] = item + 1，即当前元素的升序子序列最大长度为dp[i] = item + 1；
    注意： 在进行替换时temp[item] = s[i]，不影响后面元素的遍历，你品，你细品，很奇妙！
• 最后用总长度减去左右两边子序列之和的最大值，就是需要剔除的元素个数。

胡萝卜

2022年3月15日21:42:11

最后

以上就是悲凉蓝天为你收集整理的《华为机试》刷题之HJ24 合唱队一、题目二、示例三、代码四、算法说明的全部内容，希望文章能够帮你解决《华为机试》刷题之HJ24 合唱队一、题目二、示例三、代码四、算法说明所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。