LIS

LIS (최장증가부분수열)

LIS(Longest Increasing Subsequence)는 원소가 n개인 배열에서 일부 원소를 골라내어 만든 부분 수열 중에서 모든 원소들이 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열이다. 예시를 들어보자. A = {10, 20, 10, 30, 20, 50}인 수열에서 원소가 증가하는 부분 수열은 {10, 20}, {20, 30, 50}, {10, 30, 50} 등이 있는데, 그 중 길이가 최대인 부분 수열은 길이가 4인 {10, 20, 30, 50}이다. 대표 문제는 아래와 같다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오..