Part7.5ダイナミックプログラミング(Dynamic Programming)最大線接続(LISアプリケーション)


最大線の接続

以前と同じコード
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)