Part7.5ダイナミックプログラミング(Dynamic Programming)最大線接続(LISアプリケーション)
4718 ワード
最大線の接続
以前と同じコード
以前と同じコード
import sys
sys.stdin = open("input.txt", "rt")
n= int(input())
arr = list(map(int,input().split()))
res = 0
dy = [0]*(n+1)
dy[1] = 1
# 긴 증가수열을 만들기
arr.insert(0,0)
for i in range(2,n+1):
max = 0
for j in range(i-1, 0, -1):
if arr[j] < arr[i] and dy[j] > max:
max = dy[j]
dy[i] = max+1
if dy[i] > res:
res = dy[i]
print(res)
Reference
この問題について(Part7.5ダイナミックプログラミング(Dynamic Programming)最大線接続(LISアプリケーション)), 我々は、より多くの情報をここで見つけました https://velog.io/@angel_eugnen/Part7.5동적프로그래밍DynamicProgramming최대선-연결하기LIS응용テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol