Removing elements to sort array

Question

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?

Why not check if each succeeding element is larger than the previous element (and delete it if it's not)? — ASGM
– ASGM, Commented Apr 8, 2013 at 10:29
@ASGM: Because that "greedy" algorithm does not give the longest ascending sub-array. Consider: 9 1 2 3 4 5 6 7 8. — Thomas
– Thomas, Commented Apr 8, 2013 at 10:31

Thomas · Accepted Answer · 2013-04-08 10:31:09Z

9

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

answered Apr 8, 2013 at 10:31

Thomas

183k57 gold badges383 silver badges510 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Joost Over a year ago

Awesome, thanks! What a difference it makes to know the correct terms to search for ;)

MissingNumber · Accepted Answer · 2013-04-08 10:34:54Z

3

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

answered Apr 8, 2013 at 10:34

MissingNumber

1,18215 silver badges29 bronze badges

Collectives™ on Stack Overflow

Removing elements to sort array

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related