What is wrong with the algorithm for finding the largest non-decreasing subsequence?

Question

Programming

Good afternoon.
I'm having trouble finding the largest non-decreasing sequence in O(nlogn) time . It is necessary to calculate the length and restore the indices of the elements of the subsequence.
Everything seems to be simple, to have two arrays (one to store the current subsequence, and the other to write the indexes of the added elements). The first array is filled with some large values, and the leftmost element is set to the smallest. And with the help of binary search, we find exactly where to insert the element we are looking for.
The result is this code:

template <typename Cont>
Cont lis_bottom_up(const Cont& numbers) {
  const auto len = numbers.size();
  vector<int> d(len + 1);
  vector<int> prev(len, no_prev);
  d.front()= inf_min;
  fill(d.begin() + 1, d.end(), inf_max);

  for (auto i = 0; i < len; ++i) {
    auto j = distance(d.begin(), upper_bound(d.begin(), d.end(), numbers[i]));
    if (d[j - 1] <= numbers[i] && numbers[i] < d[j]) {
      d[j] = numbers[i];
      prev[j - 1] = i;
    }
  }
  auto res = build_answer(prev);

  return res;
}

But something goes wrong and, for example, for a sequence:
2 4 4 3 5
It turns out a subsequence of the form:
2 3 4 5
All due to the fact that at the 4th step, when we meet 3, upper_bound returns the element with index 2 (d[2] = 4; d[1 ] = 2; d[0] = inf_min) and according to the current conditions nothing prevents us from inserting this element between them.
All this is due to incorrect conditions, but I have not yet figured out how to change them.
I would really appreciate it if someone could point me in the right direction.

Answer 1

In this problem, the "current subsequence" cannot be dispensed with. It is necessary to keep the longest subsequences ending in different elements (the larger the element, the longer the subsequence ending in it should be), and when a new element arrives, then join it to the longest of the sequences to which it is possible (moreover, the old sequence should be immediately thrown away impossible - it can still come in handy), and then discard the non-optimal ones (sequence of the same length as the other, but ending with a larger element).
For example, for the sequence [1,2,7,8,9,5,6,3] you have to remember
[1,2,7,8,9]
[1,2,5,6]
[1,2,3 ]
[1,2]
[1]
Any of these sequences can be the beginning of a correct answer.
So your starting point is correct. But the vector d should not store numbers, but their indices (and the search should be more complicated), and the prev array should be modified like this: prev[i]=d[j-1].
For example [1,2,7,8,9,5,6,3] we get
d={-1,0,1,7,6,4,-1,-1,-1,...}, prev={-1,0,1,2,3,1,5,1}
(value -1 is used to indicate "no such index").