가장 긴 증가하는 부분 수열 - 동적 프로그래밍 - 2021/05/03

가장 긴 증가하는 부분수열이란 부분수열중에서 증가하는부분이 가장 긴 부분을 뜻한다.

 

예를들어, 10 20 10 30 20 50이라는 수열이 있을 때 10 20 10 30 20 50 진하게 칠해진 부분의 수열을 뜻한다.

 

n=int(input())
arr=list(map(int,input().split()))

d=[1]*n

for i in range(1,n):
    for j in range(0,i):
        if arr[j]<arr[i]:
            d[i]=max(d[i],d[j]+1)
            
print(max(d))

길지 않은 알고리즘이지만 알고리즘을 모르는상태에서는 구현하기 힘든 알고리즘 중 하나이다.

 

시간이 조금만 지나도 자꾸 잊어버려서 자주자주 연습을 해야겠다.