题解 | 拦截导弹

import sys
n = int(input())
a = list(map(int, input().split()))
b = a.copy()

redp = [1 for i in range(n)]
dp2  =[1 for i in range(n)]
for i in range(n - 2, -1, -1):
    # redp[i] = redp[i + 1]
    for j in range(i + 1, n):
        if a[i] >= a[j]:
            redp[i] = max(redp[i], redp[j] + 1)

for i in range(1, n):
    for j in range(i):
        if a[i] > a[j]:
            dp2[i] = max(dp2[i], dp2[j] + 1)

print(max(redp))
print(max(dp2))

Q2：根据Dilworth定理:最少的下降序列个数就等于整个序列最长上升子序列的长度