배열을 정렬하기 위해 요소 제거

Question

배열을 정렬하는 알고리즘을 찾고 있지만 값을 이동하지는 않습니다. 오히려 가능한 한 적은 수의 값을 삭제하고 정렬 된 목록으로 끝내고 싶습니다. 기본적으로 나는 오랜 오름차순 하위 배열을 찾고 싶다.

는 설명하기 위해 : 나는 나는이 작업을 수행하는 방법을 볼 수 있습니다

이

1 4 5 6 7 2 3 8 

이

1 4 5 6 7 8 

과하지 (5 개 제거합니다)

1 2 3 

될 (2 개 제거합니다)해야 순진한 방법, 즉 재귀 적으로 각 요소에 대한 '제거'및 '제거하지 않음'트리를 확인하는 것입니다. 더 빠르고 효율적인 방법이 있는지 궁금합니다. 이런 종류의 문제에 대한 공통적 인 이동 알고리즘이 있습니까?

Answer 1

당신은 longest increasing subsequence 문제를 찾고 있습니다. O (n log n) 시간에이를 해결하는 algorithm이 있습니다.

Answer 2

재귀 알고리즘보다 빠른 O (NlogN) 알고리즘이 사이트에서 하나 있습니다.

http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence