[BOJ 11053]最長成長部分数列(Python)
質問する
https://www.acmicpc.net/problem/11053
数列の要素を選択し、最も長い部分数列を生成し、その数列の長さを出力します.
問題を解く
dp[i]=最長配列長(i>=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)Reference
この問題について([BOJ 11053]最長成長部分数列(Python)), 我々は、より多くの情報をここで見つけました https://velog.io/@uoayop/BOJ-11053-가장-긴-증가하는-부분-수열Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol