How to find longest monotonic sequence?

  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 suppose it is faster to put everything into one compiled function, but here is a solution using Compile.

cfu = Compile[
  {{ints, _Integer, 1}},
  Block[{prev, next, startSeq, bag},

   startSeq = ints[[1]];
   prev = startSeq;
   bag = Internal`Bag[{1}];
   Do[
    next = ints[[ii]];
    If[
     next < prev,
     Internal`StuffBag[bag, ii];
     ];
    prev = next
    ,
    {ii, 2, Length@ints}
    ];
   Internal`BagPart[bag, All]
   ]
  ,
  CompilationTarget -> "C"
  ]

longestAscendingSeq[list_] :=
 Module[{starts, diffs, maxDiff, maxDiffPos, longestStart},
  starts = cfu[list];
  diffs = Differences@starts;
  maxDiff = Max@diffs;
  maxDiffPos = Position[diffs, maxDiff][[1, 1]];
  longestStart = starts[[maxDiffPos]];
  list[[longestStart ;; longestStart + maxDiff - 1]]
  ]

This gives

longestAscendingSeq[list]
{1,3,5}

Regarding question 2, there's simple algorithm finding longest sub-sequence, of elements with consecutive positions, in single pass over given list.

Function generator returning compiled functions, using this algorithm, can look like this:

compileLongestAscSubseq // ClearAll
compileLongestAscSubseq[
  {type_, rank_Integer /; rank >= 1},
  comparisonFunc : Except@OptionsPattern[] : Less,
  opts : OptionsPattern@Compile
] := Compile[{{list, type, rank}},
  Module[{start, end, bestStart, bestEnd, len, prev, curr},
    len = 0;
    start = end = bestStart = bestEnd = 1;
    prev = Compile`GetElement[list, 1];
    Do[
      curr = Compile`GetElement[list, i];
      If[comparisonFunc[prev, curr],
        end = i;
      (* else *),
        If[len < end - start,
          bestStart = start;
          bestEnd = end;
          len = bestEnd - bestStart;
        ];
        start = end = i
      ];
      prev = curr
      ,
      {i, 2, Length@list}
    ];
    If[len < end - start,
      bestStart = start;
      bestEnd = end
    ];
    Take[list, {bestStart, bestEnd}]
  ],
  opts
]

Let's compile functions taking one-dimensional arrays of integers and reals:

longestAscSubseqI1 = compileLongestAscSubseq[{_Integer, 1}, CompilationTarget -> "C", RuntimeOptions -> "Speed"];
longestAscSubseqR1 = compileLongestAscSubseq[{_Real, 1}, CompilationTarget -> "C", RuntimeOptions -> "Speed"];

Comparison with Jacob Akkerboom's longestAscendingSeq and Carl Woll's longestAscendingSubsequence on list of integers:

SeedRandom@0;
list = RandomInteger[10^6, 10^6];

(result1 = longestAscendingSeq@list) // MaxMemoryUsed // RepeatedTiming
(result2 = longestAscendingSubsequence@list) // MaxMemoryUsed // RepeatedTiming
(result3 = longestAscSubseqI1@list) // MaxMemoryUsed // RepeatedTiming
result1 === result2 === result3
(* {0.041, 16505016} *)
(* {0.051, 25128960} *)
(* {0.0038, 584} *)
(* True *)

longestAscSubseqI1 is over ten times faster and uses almost no additional memory.

Comparison with ybeltukov's longest1 and longest2 and Carl Woll's longestAscendingSubsequence on list of reals:

SeedRandom@0;
list = RandomReal[NormalDistribution[], 10^6];

(result1 = longest1@list) // MaxMemoryUsed // RepeatedTiming
(result2 = longest2@list) // MaxMemoryUsed // RepeatedTiming
(result3 = longestAscendingSubsequence@list) // MaxMemoryUsed // RepeatedTiming
(result4 = longestAscSubseqR1@list) // MaxMemoryUsed // RepeatedTiming
result1 === result2 === result3 === result4
(* {0.467, 79999584} *)
(* {0.12, 48000904} *)
(* {0.056, 25131104} *)
(* {0.0051, 608} *)
(* True *)

longestAscSubseqR1 is over ten times faster than longestAscendingSubsequence and uses almost no additional memory.