The largest total increasing sequence

The more general problem of finding the largest common subsequence (for the case of two sequences) is solved by dynamic programming in O(N*M).

The related problem of finding the largest common substring in two strings (the alphabet is bounded) is solved by suffix trees in O(N+M).

I think the truth is somewhere near). The idea is to use the condition of increasing the subsequence.

It's also worth looking at suffix trees.

It seems to me that somewhere here an error or inaccuracy of the wording has crept in. Even the problem of finding the largest increasing subsequence of a given sequence is solved in the general case for O (n log n), and here it is required for O (n + m) to find the largest common such subsequence for a pair of sequences?

Maybe they meant substrings after all? If the original sequences increase, then the solution has already been given. If not, you can divide them into increasing sections (the answer can't cross the border of such sections) and try to achieve the desired asymptotic behavior (I don't know if it will work). You can also really apply suffix trees, more precisely, this algorithm. It seems to be easy to modify it for increasing substrings, going only along increasing paths in the tree.

I managed to solve it only in O (n^2). I don't think it will be much faster. here is the code

int comlen( char *p, char *q) {
    int maxlen = 0;
    while ( (*p != '\0' || *q != '\0' ) && *p++ == *q++)
         ++maxlen;
    return maxlen;
}
int isInc( char *p, int len) {
    int i = 1;
    int k = 0;
    for (; *p != '\0' && i < len; ++i, ++k) {
         if (p[i]<p[k])
         return 0;
     }
     return 1;
}
int lcis(char * str1, char * str2, int len) {
    int maxlen = -1;
    int thislen = -1;
    int maxi = 0, maxj = 0;
    for (int i = 0; i < len; ++i){
        for (int j = 0; j < len; ++j) {
           thislen = comlen( &str1[i], &str2[j]);
               if (isInc(&str1[i], thislen)){
                   if (thislen > maxlen) {
                       maxlen = thislen; 
                       maxi = i;
                       maxj = j;
                   }
               }
         }
    }
    return maxlen;
}

There is an algorithm 0 (n~m). Something between n and m.
The meaning is as follows:

• there are global iterators (or pointers) to:
  • start in the first sequence, initially = 0
  • start in the second sequence, initially = 0
  • sequence length, initially = 0
• current variables
• start in the first sequence, initially = 0 // always equal to 0 if we are not in the general sequence subsequences
• start in the second sequence, initially = 0 / / always equal to 0, unless we are in a common subsequence
  
• sequence length, initially = 0
• there are some current pointers and a loop condition

   for (iterator i1 = listN.begin(), iterator i2=listM.begin(); i1!=listN.end() && i2!=listM.end(); )
   {
       if (мы не в общей подпоследовательности)
       {
          if (*il=*i2)
          {
             то начинаем новую подпоседовательность, заодно длина текущей подпоследовательности ++;
             ++i1;
             ++i2;
          }
          else
          {
             сдвигаем тот итератор, значение по которому меньше;
          }
       }
       else if (мы в общей подпоследовательности)
       {
          if (*il=*i2)
          {
             длина текущей подпоследовательности ++;
             ++i1;
             ++i2;
          }
          else
          {
             общая подпоследовательность закончилась,
             сравниваем ее с найденной глобальной; 
             если текущая больше глобальной, приравниваем глобальную текущей;
             ставим текущие начала последовательности в NULL, 
             а текущую длину подпоследоваельности в 0;
             сдвигаем тот итератор, значение по которому меньше;
          }
       }
   }

After passing the loop, the global variables will contain the result: if there was a subsequence, then either both iterators are iterated, if the values for them are equal, or 1 of them, for which the value is greater until the end of one of the lists is reached.

I suggest paying tribute to this article: Longest increasing subsequence in O (N log N)