# How to find longest monotonic sequence?

I have a list, for example

list = {2, 1, 3, 5, 4, 6}


How to find longest ascending sequence of this list?

There are two meanings of this question:

1. Find the largest subset that $$X_{i_1} < X_{i_2} < \ldots < X_{i_{n-1}} < X_{i_n}$$ where $$i_1 < i_2 < \ldots < i_{n-1} < i_n$$

2. Find the largest subsequence that

$$X_i < X_{i+1} < \ldots < X_{j-1} < X_{j}$$

-

1. There is an undocumented function LongestAscendingSequence

LongestAscendingSequence[list]

{1, 3, 4, 6}


This was mentioned here and here in comments. I hope it will not be treated as a duplicate. I think Q&A-style on SE is more appropriate for this question.

2. For completeness I ask the second question. It seem to be much simpler but I can't find any simple function. My own answer:

longest1[list_] := #[[Position[#, Max[#]][[1, 1]] &[Length /@ #]]] &@ Split[list, Less];
longest2[list_] := list[[#2 - # ;; #2 &[Max[#], Position[#, Max[#]][[1, 1]]] &@
FoldList[(#1 + #2) #2 &, 0, UnitStep@Differences[list]]]];

longest1[list]
longest2[list]

{1, 3, 5}
{1, 3, 5}


longest2 is faster for big lists:

RandomSeed[0];
list = RandomReal[NormalDistribution[], 1000000];

longest1[list] // AbsoluteTiming
longest2[list] // AbsoluteTiming

{0.925531, {-2.15449, -1.60199, -0.903194, -0.678062, -0.294706,
-0.270457, 0.219321, 0.677958, 1.07586}}
{0.228277, {-2.15449, -1.60199, -0.903194, -0.678062, -0.294706,
-0.270457, 0.219321, 0.677958, 1.07586}}

-
I doubt this is "undocumented" in the real sense of the word... it's more likely that it was an oversight in writing the documentation for it. Nevertheless, this is not a duplicate, so thanks for asking&answering to document it! :) – R. M. Oct 18 '13 at 17:26
+1. The shortest way previously known to me using built-ins is LongestCommonSequence[list, Sort@list], but LongestAscendingSequence is quite a bit faster. I may add another answer later which uses Compile, if I see that it is competitive with LongestAscendingSequence . – Leonid Shifrin Oct 18 '13 at 18:46
For the second one I'd use MaxBy[Split[list, Less], Length], utilizing MaxBy, which is part of my "mental toolbox". (Note that MaxBy will only return a single result even if there are several equivalent maximal elements.) – Szabolcs Dec 6 '13 at 14:54
@LeonidShifrin did you find that the compiled approach was uncompetitive, or did you just not have time to try it? This was my first thought as well, and it would be interesting to know whether LongestAscendingSequence is really as fast as it can be, or whether one can do better. – Oleksandr R. Dec 7 '13 at 21:09
@OleksandrR. I just did not have the time. I don't have a C compiler installed on a machine I work with currently most of the time, and the last few months were very busy. Later, I forgot about it. If I don't forget this time, I will test this, and report my findings here - but I can't promise when this happens :) – Leonid Shifrin Dec 7 '13 at 22:28