최대부분증가수열 찾기 |
---|
수열 A를 구성하는 각각의 수를 A[i]라고 하자. 이때 A[i]는 수열 A를 구성하는 i번째 수를 의미하며 A[i]는 수열 A의 부분수열이다. 또한 i < j 인(i와 j가 연속할 필요는 없다) 임의의 i와 j에 대해서 A[i]A[j]도 수열 A의 부분수열이다. 여기에 j < k 인(j와 k도 연속할 필요는 없다) 임의의 k번째 수 A[k]를 덧붙인 A[i]A[j]A[k]도 수열 A의 부분수열이다. 3 1 2 6 4 7 5 9 이런 식으로 한다면 위의 수열에서 3 등 무수히 많은 부분수열이 존재한다. 그러나 위에서 언급한 규칙상 다음의 수열 2 1 등은 부분수열이 될 수 없다. 부분수열에서 i < j 인 임의의 i와 j에 대해서 A[i]<A[j]를 만족한다면 이 수열을 ‘부분증가수열’이라고 하며, 그러한 부분증가수열의 길이가 최대가 되는 수열을 ‘최대부분증가수열’이라고 한다. 1 2 위의 부분수열이 모두 ‘부분증가수열’이며 1 2 4 5 9, 1 2 6 7 9은 그 길이가 최대인 ‘최대부분증가수열’이다(하나의 수열에 대해서 최대부분증가수열은 반드시 1개 이상 존재한다). 현재 최대부분증가수열의 길이는 5다. 하나의 수열이 주어질 때 최대부분증가수열(Longest Increasing Subsequence)의 길이를 출력하는 프로그램을 작성하시오. |
입력 | |
---|---|
입력 파일은 2개의 줄로 구성된다. 첫 번째 줄에 수열의 길이가 주어지고, 두 번째 줄에 수열이 주어진다. 단, 수열을 구성하는 각 수들은 공백을 사이에 두고 주어진다. 수의 범위는 1 ~ 10000 이고, 수열의 길이는 1 ~ 10000 이다. |
출력 | |
---|---|
첫 번째 줄에 주어진 수열의 최대부분증가수열의 길이를 출력한다. |
예시 | |||
---|---|---|---|
1 | 입력 | 8 3 1 2 6 4 7 5 9 | |
출력 | 5 | ||
2 | 입력 | 9 0 22 9 33 21 50 41 60 80 | |
출력 | 6 |