문제 설명 N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다.
입력 설명 첫째 줄은 입력되는 데이터의 수 N(1≤N≤1,000, 자연수)를 의미, 둘째 줄은 N개의 입력데이터들이 주어진다. 출력 설명 첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
예제 입력 8 5 3 7 8 6 2 9 4 출력 입력 4 첫 번째 풀이 시도 DP임을 알고 시도한 문제였는데, 어떻게 접근해야될지 몰라서 일단 완전 탐색으로 접근해보았다. 자리수가 최대 1000자리까지 나옴에도 불구하고 일단은 모든 경우의 조합을 구하고, 그 안에서 부분 증가 수열의 최대 길이를 측정하는 방식으로 시도해보았다.
당연히 시간...
원문 링크 : 최대 부분 증가수열
