最大線の接続

3953 ワード
python アルゴリズム#アルゴリズム# テキストリンク
作成日:2022年2月23日午後6:29

インプリメンテーションコード

# 최대 선 연결하기
import sys
#sys.stdin = open("in4.txt" ,"rt")

n = int(input())
arr = list(map(int, input().split()))
arr.insert(0, 0)
dy = [0]*(n+1)

dy[1] = 1

for i in range(2, n+1):
    maxNum = 0
    for j in range(1, i):
        if arr[j] < arr[i]:
            if dy[j] > maxNum:
                maxNum = dy[j]
    dy[i] = maxNum + 1

print(max(dy))
  • 問題は異なるように見えますが、最大部分に数列を増やすなどの問題があります.
  • why? 与えられた数値では、最大増加数列に対応する値が最も多くの直線に接続できるからである.
    • いちばん高い塔を建てる
    最大ローカル増分数列