≪水平｜Horizontal｜Eas≫-最も長く成長した部分数列(11053)
Dynamic Programming
質問する
数列Aが与えられると、最も長い部分の数列を求めるプログラムが作成される.
例えば、A={10,20,10,30,20,50}を数える場合、最も長くなる部分はA={10,20,10,30,20,50}であり、長さは4である.
入力
第1行は、数列AのサイズN(1≦N≦1000)を与える.
2行目は、数列Aを構成するAiを与える.(1 ≤ Ai ≤ 1,000)
しゅつりょく
第1行出力数列Aの最長増分部分数列の長さ.
import sys
input = sys.stdin.readline
n = int(input())
A = [int(x) for x in input().split()]
DP = [1 for i in range(n)]
for i in range(n):
for j in range(i + 1): # 0부터 자기 자신(i)까지 범위 탐색
if A[i] > A[j]: # 대소 비교
DP[i] = max(DP[i], DP[j] + 1)
# DP[i] => 기존 자기자신까지의 증가수열 최대 길이
# DP[j] + 1 => i보다 작은 인덱스 j의 최대 길이값 + 1(i까지 증가수열의 길이로 포함)
# 결국 i의 DP값과 (j의 DP값 + 1)을 비교해서 값 갱신
print(max(DP))https://velog.io/@simonyun 97/白準-11053-問題-最長-増分-部分-数列LIS
Reference
この問題について(≪水平｜Horizontal｜Eas≫-最も長く成長した部分数列(11053)), 我々は、より多くの情報をここで見つけました https://velog.io/@skkfea07/백준-가장-긴-증가하는-부분-수열11053テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol