[Python]11053. 가장 긴 증가하는 부분 수열 (LIS)

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

11053번: 가장 긴 증가하는 부분 수열

---

아이디어를 떠올리기 어려웠다.

LIS 는 굉장히 중요한 문제이므로 연습이 필요하다.

 

정답은

부분수열이므로, 특정 시점에서 (i) 에서 맨 앞쪽까지 크기 비교를 수행한 뒤,

가장 큰 길이(DP 값)를 구해서 마지막에 자기자신(+1)을 더한다.

 

즉 D[i] = max(D[i-1], D[i-2], ... , D[2], D[[1]) + 1 이다.

n = int(input())
a = [0]+list(map(int, input().split()))
DP = [0]*(n+1)

for i in range(1,n+1):
    for j in range(1, i, 1):
        if a[i] > a[i-j]:
            DP[i] = max(DP[i-j], DP[i])
    DP[i] += 1
print(max(DP))