[Algorithm] 최장 증가 부분 수열(LIS)
원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. {6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 {2, 5, 8, 7} 이고, 길이는 4 {2, 5}, {2, 7} 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것은 {2, 5, 8, 7} {10, 20, 10, 30, 20, 50} 이라는 배열이 있을 경우, LIS는 {10, 20, 30, 50} 이고, 길이는 4 D[i] = arr[i]를 마지막 원소로 가지는 부분 수열의 최대길이 라고 정의할 때, 가장 긴 증가하는 부분 수열을 계산하는 점화식을 작성해보면, 다음과 같다. (DP 테이블..
