[DP] LIS ( Longest Increasing Subsequence)

LIS 란 제시된 수열에서 증가된 부분 수열 중 가장 길이가 긴 것을 말한다. 예를 들어보자. 수열 { 1 , 4 , 5 , 2, 3 , 9 , 20, 11 } 이 있다고 하자. 이 중에서 증가 부분 수열은 { 1, 5 , 9 , 11 } 이 될 수도 있고 { 4 , 5 , 9 , 11 } 이 될 수도 있다. 하지만 우리가 찾는 LIS라 불리는 부분수열은 { 1, 4, 5, 9, 11 } 이 될 것이다. LIS 구현 방법 순서 리스트의 첫 번째 값을 LIS 배열에 넣자. LIS 배열의 마지막 인덱스 값이 리스트의 값과 비교를 한다. 리스트의 값 > LIS.get(마지막인덱스) LIS 배열 ADD ( 리스트의 값 ) 리스트의 값 < LIS.get(마지막인덱스) LIS배열에서 리스트의 값보다 작아지는 최초 ..

2020.06.19