题解 | 拦截导弹

import sys
def dp(num,height):
    dp=[1]*num
    for i in range(1,num):
        for j in range(0,i):
            dp[i]=max(dp[j]+1,dp[i]) if height[j]>=height[i] else dp[i]
    print(max(dp))
if __name__=='__main__':
    it=iter(sys.stdin)
    while 1:
        try:
            num=int(next(it).strip())
            height=list(map(int,next(it).strip().split()))
            dp(num,height)
        except:
            break

可以抽象为最长非递增子序列问题，定义dp数组为以height[i]结尾的最长非递增子序列的长度，计算完之后，求最大值