paizaラーニング問題集「【部分列】最長減少部分列」を解いてみた

▼感想

前問「最長部分増加列」と考え方は同じかと思います。
a_j(jは1～i-1) > a_i が成り立つとき、
最初が木a_jであるような減少部分列の末尾に木をくっつけて、
dp[i]+1の減少部分列を作ることができる。

▼コード

########## 処理0(準備) インプット,リスト定義など ###########

n = int(input())

a = [0]*n

########## 処理1 漸化式の定義、計算、出力 ##########

dp = [0]*n

dp[0] = 1

for i in range(n):
    a[i] = int(input())

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

print(max(dp))