수열 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
1
2
...
3 1
3 1 2
4 5
2 6 4
2 6 4 9
3 1 4 7 5
...
3 1 2 6 4 7 5
3 1 2 6 4 7 5 9
...

등 무수히 많은 부분수열이 존재한다. 그러나 위에서 언급한 규칙상 다음의 수열

2 1
4 1 3
4 1
...

등은 부분수열이 될 수 없다.

부분수열에서 i < j 인 임의의 i와 j에 대해서 A[i]<A[j]를 만족한다면 이 수열을 ‘부분증가수열’이라고 하며, 그러한 부분증가수열의 길이가 최대가 되는 수열을 ‘최대부분증가수열’이라고 한다.

1 2
1 2 6 7 9
2 6
2 6 7 9
4 5
4 5 9 7 9
...
1 2 4 5 9
...

위의 부분수열이 모두 ‘부분증가수열’이며 1 2 4 5 9, 1 2 6 7 9은 그 길이가 최대인 ‘최대부분증가수열’이다(하나의 수열에 대해서 최대부분증가수열은 반드시 1개 이상 존재한다).

현재 최대부분증가수열의 길이는 5다.

하나의 수열이 주어질 때 최대부분증가수열(Longest Increasing Subsequence)의 길이를 출력하는 프로그램을 작성하시오.