백준 11053 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

 

이 문제는 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제이다.

 

예를 들어 [10,20,10,30,40] 이란 수열이 있다면 이중 가장 긴 증가하는 부분수열은 [10,20,30,40]으로 길이가 4이다. 이 문제는 다이나믹 프로그래밍을 이용하여 풀 수 있다. 수열 위를 훑어가며 지금 이 인덱스에서 가장 길게 형성된 수열을 자신의 앞에서 찾으며 더 이어갈 수 있는지를 체크하며 풀면 된다.

 

def lgis(seq,l):
    p = [-1] * l #거리

    for i in range(l):
        for j in range(i):
            if seq[j] < seq[i] and p[j]+1 > p[i]:#증가하고, 더 길다면
                p[i] = p[j]+1

    return max(p)+2

N=int(input())
A = list(map(int,input().split()))

print(lgis(A,N))