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

質問する

https://www.acmicpc.net/problem/11053

数列の要素を選択し、最も長い部分数列を生成し、その数列の長さを出力します.

問題を解く

dp[i]=最長配列長(i>=1)で、数列の最初の要素を作成できます.

の部分数列の値を増やさなくても、各要素の配列長は1になります.
したがって、dpのすべての値を1にリセットします.dp = [1] * n

以前の数字と比べると、if nums[i] > nums[j]:dp[i]をdp[j]+1の最大値に変換します.dp[i] = max(dp[i],dp[j]+1)

コード#コード#

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int,input().rsplit()))
dp = [1] * n

# i = 0, j = 0
# i = 1, j = 0, 1 
# i = 2, j = 0, 1, 2 ...
for i in range(n):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i],dp[j]+1)

print(dp)