Find longest monotonically increasing subsequence containing final two elements

Using Leonid Shifrin's solution from the Q&A you mentioned:

longestSequence[{seq___, a_, b_}] := With[{list = Select[{seq}, # < a &]},
  Join[LongestCommonSequence[list, Sort@list], {a, b}]
  ]

This is sufficiently different from my other answer. I have, therefore,chosento post it separately.

func[ls_] := 
 Module[{tag = Thread[{Range[Length@ls], ls}], gr, vl, jn, mx},
  gr = RelationGraph[#2[[1]] > #1[[1]] && #2[[2]] > #1[[2]] &, tag];
  vl = VertexList[gr];
  jn = Join @@ (Catch[
        Do[With[{w = FindPath[gr, #, tag[[-2]], {n}]}, 
          If[Length@w != 0, Throw[w], If[n == 1, Throw[{}]]]], {n, 
          Length@ls, 1, -1}]] & /@ vl);
  mx = Max[Length /@ jn];
  {mx + 1, #[[All, 2]]~Join~{ls[[-1]]}, 
     HighlightGraph[gr, ##~Join~{tag[[-1]]}, 
      VertexLabels -> 
       Table[j -> Framed[j[[2]], Background -> White], {j, vl}], 
      Prolog -> {Red, Thick, 
        Line /@ Partition[
          GraphEmbedding[
            gr][[##~Join~{tag[[-1]]} /. 
             Thread[vl -> Range[Length[vl]]]]], 2, 1]}, 
      ImageSize -> {400, 400}]} & /@ Pick[jn, Length[#] == mx & /@ jn]
  ]

There is a lot of 'window dressing' that can be removed. The output is the length of longest strictly increasing subsequence terminating in the last two entries of given sequence., some examples and the highlighted graph.

Tesing:

lst = {3, 4, 6, 7, 5, 8};
Column[Column[#, Alignment -> Center] & /@ func[lst], 
 Alignment -> Center, Frame -> True]

ri = RandomInteger[{1, 10}, 15]~Join~{5, 8}
Row[Column[#, Frame -> True, Alignment -> Center] & /@ func[ri]]

Just for fun, since obvious solutions already posted. Returns the length that OP requested, quite quick...

longSeq= Compile[{{lst, _Integer, 1}},
  Module[{ba = Pick[lst, UnitStep[lst[[-1]] - lst], 1], ta, c1=1, m1 = 0},
   ta = ConstantArray[Max@ba + 1, Length@ba];
   Do[
      While[ta[[c1]] < ca, c1++];
      ta[[c1]] = ca; 
      m1 = Max[m1, c1];
      c1=1;
    , {ca, ba}];
   m1]
  ];

More to the point, this is very fast:

longSeq2=Length[LongestOrderedSequence[Pick[#,UnitStep[#[[-1]]-#],1]]]&;