Given an array, find maximal sorted subset [duplicate]

Question

I want to find the maximal subset of an array which is sorted in ascending order

Say I have

a = [2, 1, 4, 6, 7]
a_max_subset = [1, 4, 6, 7]

b = [4, 1, 2]
b_max_subset = [1, 2] 

c = [2, 5, 13, 8, 6, 23, 33]
c_max_subset = [2, 5, 8, 23, 33]

Is there an efficient way to do this ?

I don't think there can be anything better than O(n) anyway, as you really have to though the array from beginning to end. — Some programmer dude
– Some programmer dude, Commented Jul 9, 2015 at 4:11
Do the elements have to appear consecutively in the original array? e.g. c = [3, 6, 4, 5, 7], is c_max_subset [3, 4, 5, 7] or [4, 5, 7]? — samgak
– samgak, Commented Jul 9, 2015 at 4:23

Karthik · Accepted Answer · 2015-07-09 07:33:37Z

0

What you are trying to find out is Longest increasing subsequence.

You can find an O(N^2) implementation here. It's well explained and commented properly. Try to understand the explanation and implement it by yourself.

If you are really curious, you can check this O(N logN) solution also.

answered Jul 9, 2015 at 7:33

Karthik

5,0387 gold badges39 silver badges67 bronze badges

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

Collectives™ on Stack Overflow

Given an array, find maximal sorted subset [duplicate]

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related