最大線の接続(LISアプリケーション)

ダイナミックプランニング

に質問

最大線の接続(LISアプリケーション)

左側の番号と右側の番号の図で、同じ番号を同じ直線に接続しようとします.左の番号は無条件に上から下へ1からNまで昇順に並べられています.右側の番号情報を上から下へ順番に与えるが、互いに重ならず、最大何本の線を接続できるかを求めるプログラムを作成してください.

上図に示すように、右番号情報が4 1 2 3 9 7 5 6 10 8と入力されると、重ならず接続可能な最大直線数が6となるように求められる.
■説明の入力
第1行は自然数N(1<=N<=100)を与える.
2行目は、1からNまでの自然数N個の右番号情報を提供する.上から順に:
■出力説明
最初の行に描画できる最大行数を出力します.
■入力例1
10
4 1 2 3 9 7 5 6 10 8
■出力例1
6

コード#コード#💻

import sys
#sys.stdin = open("input.txt", "rt")            # read text

n = int(input())
arr = list(map(int, input().split()))
arr.insert(0, 0)                                # 1번 인덱스부터 시작
dy = [0] * (n+1)
dy[1] = 1                                       # 1번 인덱스는 무조건 길이 1
res = 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)

リファレンス

インフラストラクチャ:Pythonアルゴリズム回答