Given an array, find maximal sorted subset

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 ?

[Largest increasing subsequence](https://en.wikipedia.org/wiki/Longest_increasing_subsequence) perhaps? — Alejandro, Jul 09 '15 at 04:08
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, Jul 09 '15 at 04: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, Jul 09 '15 at 04:23
@Tony wanted the ascending order subset, thanks! for pointing this out. Have edited the question — vin, Jul 09 '15 at 06:18
Using subset is misleading. As in sets (and also in subsets) order is not important (, and there is no duplicates). — Nuri Tasdemir, Jul 09 '15 at 06:52

score 0 · Answer 1 · answered Jul 09 '15 at 07:33

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.

Given an array, find maximal sorted subset

1 Answers1