题解 | #合唱队#【左右互博法】

合唱队

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

把两个双重for循环做成一个,但是依旧超时。

n = int(input())
hgt = list(map(int, input().split(' ')))
ldp = [1] * n 
rdp = [1] * n 
for i in range(1, n):
    for j in range(i):
        ii, jj = -i - 1, -j - 1
        if hgt[i] > hgt[j]:
            ldp[i] = max(ldp[i], ldp[j] + 1)
        if hgt[ii] > hgt[jj]:
            rdp[ii] =max(rdp[ii], rdp[jj] + 1)

print(n - max([i + j - 1 for i, j in zip(ldp, rdp)]))
全部评论

相关推荐

点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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