Finding All possible Longest Increasing subsequence

Question

I want to find all possible Longest Increasing Subsequences in a given string.

For eg: Given string is qapbso

Here the length of longest increasing subsequence is 3. I want to find all possible longest subsequence of length 3. i.e "abs", "aps", "abo".

I am using Dynamic Programming but I am only getting one LIS. I want to list down all of them.

Answer 1

So the typical DP solution to this will produce an array in which you know what is the longest possible subsequence starting at a given position i let's say that you have and array with length n in which dp[i] stores the length of the longest non-decreasing subseq that starts with the element with index i.

Now printing all the LNDSS(longest non-decreasing subsequences) is easiest to be done using a recursion. First find the actual length of the LNDSS by seleting the greast value in dp. Next start the recursion from each element in dp that has the maximum value in dp(these may be more then one). The recursion from a given index should print all the sequences starting from the current index that have length equal to the value dp[i]:

int st[1000];
int st_index
void rec(int index) {
  if (dp[index] == 1) {
    cout << "Another sequence:\n";
    for (int i = 0; i < st_index; ++i) {
      cout << st[i] << endl;
    }
  }
  for (int j = index + 1; j < n; ++j) {
    if (dp[j] == dp[index] - 1 && a[j] >= a[index]) {
      st[st_index++] = a[j];
      rec(j);
      st_index--;
    }
  }
}

This is example code in c++(hope it is understandable in other languages as well). I have a global stack called stack that keeps the elements we have already added. It has size 1000 assuming you will never have more then 1000 elements in the LNDSS but this can be increased. The solution does not have the best possible design, but I have focused on making it simple rather then well designed.

Hope this helps.

Answer 2

Given this graph where all nodes are connected to the nodes that have both higher value and appear later in the sequence of letters of your input string:

You want to find the longest path from START to END. This is equivalent to the shortest path if all segments have negative length of -1.

Reference on longest path problem: http://en.wikipedia.org/wiki/Longest_path_problem