LIS(Longest Increasing Subsequence, 최장증가 부분 수열)

주어진 어떤 수열에서 순서대로 증가하면서 커지는 가장 긴 수열

 

---

LIS를 찾아내는 다양한 방법을 생각하고 만들어낼 수 있지만 재귀적 문제해결사고를 활
용할 수도 있다.

1. k번째 위치를 마지막으로 만들어질 수 있는 LIS의 길이를 solve(k)라고 하자.
2. 그렇다면 solve(k)는 그 이전의 solve(k-1), solve(k-2), solve(k-3), … , solve(3), solve(2), solve(1)들의 길이에 1을 더한 것이라고 생각할 수 있다.