최대 선 연결하기

생성일: 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? 주어진 숫자들 중에서 최대 증가 수열에 해당되는 값들에서 가장 선을 많이 연결할 수 있기 때문이다.