[BOJ 11053]最長成長部分数列(Python)

質問する

質問する

問題の説明

DPを使用して、最長部分数列の問題をリフレッシュします.
まず、各インデックスiは、一部の問題に対して、0からiまでの最長数列長を含む.
DPを埋め込む方法は、iに1つずつアクセスする前の配列であり、seq[j]がseq[i]より小さい場合、dp[i]とdp[j]+1(自分が入っている場合)を比較する.

プールコード

import sys

input = sys.stdin.readline
n = int(input())
dp = [1] * n
seq = list(map(int, input().split()))

for i in range(n):
    for j in range(i):
        if seq[j] < seq[i]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))