CODEWITHSUNDEEP
algorithmsorting
Joost
Joost

Reputation: 4134

Removing elements to sort array

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?

Upvotes: 2

Views: 1606

Answers (2)

MissingNumber
MissingNumber

Reputation: 1182

There is one O(NlogN) algorithm from the site which is faster than the recursive algorithm .

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

Upvotes: 3

Thomas
Thomas

Reputation: 181785

You're looking for the longest increasing subsequence problem. There is an algorithm that solves it in O(n log n) time.

Upvotes: 9

Related Questions