쉬운 최장 증가 부분 수열 timer 1s memory 1024MB

최장 증가 부분 수열은 줄여서 LIS(Longest Increasing Subsequence)라고 부르기도 한다.

어떤 수열의 부분 수열이라 함은, 원래 수열에서 몇 개의 원소를 뽑아 순서를 유지한 채 나열한 수열을 뜻한다.

예를 들어서 수열 [7 2 5 3 4 9 1] 에서

[7 5 3 4]나 [2 9]는 부분 수열이지만,

[1 2 3 4]는 원소의 순서가 바뀌었기 떄문에 부분 수열이 아니다.

증가 수열이라 함은, 말 그대로 모든 수열의 원소가 증가하는 순서대로 나열되어 있음을 뜻한다.

부분 증가 수열은 주어진 원래 수열의 부분 수열이면서 증가 수열이기도 한 수열을 뜻한다.

최장 부분 증가 수열은 주어진 수열에서 만들 수 있는 부분 증가 수열 중에서 가장 긴 수열을 뜻한다.

우리의 목적은 주어진 수열로 찾을 수 있는 최장 부분 증가수열의 길이, 즉 LIS의 길이를 찾는 것이다.

크기 N의 수열이 주어졌을 때, 그 수열의 LIS의 길이, 즉 최장 증가 부분 수열의 길이를 찾아 출력하라.