Removing elements to sort array
algorithm, sorting
Solution
You're looking for the longest increasing subsequence problem. There is an algorithm that solves it in O(n log n) time.
Problem
I'm looking for an algorithm to sort an array, but not by moving the values. Rather, I'd like to delete as few values as possible and end up with a sorted list. Basically I want to find the longest ascending sub-array. To illustrate: ``` 1 4 5 6 7 2 3 8 ``` Should become (2 removes) ``` 1 4 5 6 7 8 ``` And not (5 removes) ``` 1 2 3 ``` I can see how I can do this in a naive way, i.e. by recursively checking both the 'remove' and 'dont remove' tree for each element. I was just wondering if there was a faster / more efficient way to do this. Is there a common go-to algorithm for this kind of problem?