题解 | #合唱队#

合唱队

https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4

##有参考大佬写的代码

N = int(input())  # 同学的总数
ls = list(map(int,input().split()))     # N位同学的身高
ls1 = [1] * len(ls)      # 存储长度  ##因为至少有一个自己本身,所以初始值设置为1
ls2 = [1] * len(ls)


# 假设正好第i位同学左右两边可以组成合唱队,那么说明i左边的都比他矮,i右边的也比他矮

# 先算左边的长度          
for i in range(len(ls)):
    for j in range(i):
       if ls[i] > ls[j] and ls1[i] < ls1[j] + 1:
           ls1[i] = ls1[j] + 1
#print(ls1)

# 再计算右边的最大长度(注意右边需要倒着来)
for i in range(len(ls)-1,-1,-1):        # 注意这个结束位置是-1,因为本来要到取到位置0,但是range()函数不包含结束位置,所以要写-1
    for k in range(len(ls)-1,i-1,-1):
        if ls[i] > ls[k] and ls2[i] < ls2[k] + 1:
            ls2[i] = ls2[k] + 1
#print(ls2)

###print(N-max(ls1)-max(ls2)+1)        # 注意,不能写成这样的

p = 0
for i in range(N): # 186 186 150 200 160 130 197 200
    if ls1[i] + ls2[i]-1 > p:       # 注意是左右两个列表的对应位置相减
        p = ls1[i] + ls2[i]-1
print(N-p)




          

全部评论

相关推荐

小叮当411:应该是1-3个月吧
点赞 评论 收藏
分享
酷酷我灵儿帅:这去不去和线不线下面说实话没啥关系
点赞 评论 收藏
分享
陆续:不可思议 竟然没那就话 那就我来吧 :你是我在牛客见到的最美的女孩
点赞 评论 收藏
分享
07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
无能的丈夫:但我觉得这个hr语气没什么问题啊(没有恶意
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务