최대 부분 증가 수열

생성일: 2022년 2월 23일 오후 5:09

구현 코드 ⭐

# 최대 부분 증가수열
import sys
sys.stdin = open("input.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):
    maxLen = 0
    for j in range(1, i):
        if arr[i] > arr[j]:
            if dy[j] > maxLen:
                maxLen = dy[j]
    dy[i] = maxLen+1

print(dy)

• i 번째 값 위치에서 가장 긴 수열은 첫번째 값부터 i-1번째 값들(j) 중에서 i보다 값이 작으면서 가장 긴 수열을 가진 값을 찾고, 해당 값에서의 수열 최대 길이에 1을 더한 것이다.