최장 증가 부분 수열(LIS) 알고리즘
원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다
핵심
•
원소 A[i]는 A[i] 전의 원소 A[k] (0 ≤ k < i) 중, 어떤 A[k] 뒤에 올 수 있는가?
•
A[i]에 대해 A[i] 앞에 올 수 있는 원소의 개수들을 관리할 수 있으면 된다
◦
memoization → DP
DP 구현 방법
1) D[i] = A[i] 까지의 LIS의 길이를 저장하는 배열을 정의
2) D[i]의 마지막 원소는 A[i]가 된다
3) 그렇다면, D[i]는 D[k] (0 < k < i, A[k] ≤ A[i])의 최댓값 +1이 된다
4) 즉, A[i]를 마지막 원소로 하는 LIS의 길이는, A[0]부터 A[i-1] 중, A[i]보다 작은 원소들에 대해
그것들을 마지막 원소로 가지는 LIS의 길이에 1을 더한 것이다
5) A[i]를 맨 뒤에 붙일 수 있는지 없는지를 따지면서, 최댓값을 갱신해가면 된다
