LIS (최장 증가 부분 수열)

✔ LIS (최장 증가 부분 수열)

• Longest Increasing Subsequence의 약자
• 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 알고리즘
• 예를 들어, { 4, 6, 4, 8, 3, 5 }라는 수열이 있을 때 만들 수 있는 증가하는 부분 수열은 { 4, 6 ,8 }, { 3, 5 }, { 4, 5 } 등 다양하지만, LIS는 가장 긴 증가 부분 수열인 { 4, 6, 8 }을 찾는 것이다.