[노트] 최장 부분수열 (LIS)

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

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

 

 

n = int(input())
arr = list(map(int, input().split()))
dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if arr[j] < arr[i] and dp[j] >= dp[i]:
            dp[i] = dp[j] + 1


print(max(dp))

 

 

1. 다이나믹 프로그래밍으로 해결할 수 있다. 
2. arr[j] < arr[i] 이고, 
3. dp[j] >= dp[i] 일 때, 
4. dp[i] = dp[j] + 1 이다. (수열의 길이가 1 늘어난다. )