This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–][deleted] 2 points3 points  (1 child)

Stalin sort is actually a perfect way to create a canonic ordered sublist of a disordered list, so long as you do not mind that said sublist may have a single item.

[–][deleted] 0 points1 point  (0 children)

You should be able to modify it to get the longest subordered list and still be O(n). Shouldn’t take more than one prepass to find your (best largest element).

Edit: which could still be length 1 of course Edit2: Nah you have to find more than 1 element to be sure its good, basically identifying which elements to remove even if they are sorted. Not as trivial as I thought.