Part7.4動的プログラミング最大インクリメンタル列
5142 ワード
最大ローカル増分数列
先生コード
2からiまで、前から1まで、最後の数字とiを比較します.
iより小さい数の中で最大の数を探します
そして+1をしてarr[i]を初期化する.
最後に、増分数列の最大値をresに初期化し続け、
出力します.
先生コード
import sys
sys.stdin = open("input.txt", "rt")
n = int(input())
arr = list(map(int, input().split()))
arr.insert(0,0)
dy = [0]*(n+1)
dy[1] = 1 # 첫번째 숫자는 앞에 아무것도 없으므로
res = 0
for i in range(2, n+1):
max = 0
for j in range(i-1, 0, -1): # i 바로 앞에서 부터 1 까지 돈다
if arr[j]<arr[i] and dy[j] > max: # 마지막 항의 바로 앞에서부터 1까지
# arr항의 바로 앞의 숫자를 찾는 행위!!
max = dy[j]
dy[i] = max+1
if dy[i] > res:
res = dy[i]
print(res)
2からiまで、前から1まで、最後の数字とiを比較します.
iより小さい数の中で最大の数を探します
そして+1をしてarr[i]を初期化する.
最後に、増分数列の最大値をresに初期化し続け、
出力します.
Reference
この問題について(Part7.4動的プログラミング最大インクリメンタル列), 我々は、より多くの情報をここで見つけました https://velog.io/@angel_eugnen/Part7.4동적프로그래밍DynamicProgramming최대부분-증가수열LISLongest-Increasing-Subsequenceテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol