Longest Common Increasing Subsequence Dynamic Programming

Question

I'm working on finding a solution to the longest common increasing sub sequence problem. Here's a link if you're not familiar with it. LCIS

The problem can basically be reduced to two different problems. 'Longest common subsequence' and 'Longest increasing subsequence'. Here's the recursive solution to Longest common subsequence:

LCS(S,n,T,m)
{
if (n==0 || m==0) return 0;
if (S[n] == T[m]) result = 1 + LCS(S,n-1,T,m-1); // no harm in matching up
else result = max( LCS(S,n-1,T,m), LCS(S,n,T,m-1) );
return result;
}

Based on that and the general recursive formula found here I've been trying to implement the algorithm so I can use dynamic programming.

int lcis(int S[4], int n, int T[4], int m, int prev)
{
  int result;

  if (n == 0 || m  == 0)
    return 1;
  if (S[n] == T[m] && S[n] > S[prev]){
    result = myMax(1 + lcis(S, n-1, T, m-1, n), lcis(S, n-1, T, m, prev),
                    lcis(S, n, T, m-1, prev)) ;
  }
  else
    result = max(lcis(S,n-1,T,m, prev), lcis(S,n,T,m-1, prev));

  return result;
}

Obviously this does not give the correct solution. Any help would be appreciated.

For example, if I give it the two sequences {1, 2, 4, 5} and {12, 1, 2, 4} I get an output of 2. The correct output here would be 3, for the sub sequence {1,2,4}

EDIT:

Here is some revised code, after suggestions from below. Still not 100% correct. But closer. Note I am now using vectors, but this shouldn't change anything.

int lcis(vector<int> S, int n, vector<int> T, int m, int size)
{
  int result;

  if (n < 0 || m < 0)
    return 0;
  if (S[n] == T[m] && (n == size - 1 || S[n] < S[n + 1] )){
    result = myMax(1 + lcis(S, n - 1, T, m - 1, size), lcis(S, n - 1, T, m, size),
                    lcis(S, n, T, m - 1, size));
  }
  else
    result = max(lcis(S, n-1, T, m, size), lcis(S, n, T, m-1, size));

  return result;
}

"Obviously this does not give the correct solution". No, it's not obvious at all. You have not shown input or expected vs actual output. If you want help, don't expect us to go off and follow web links to understand the problem and then try to match it to your algorithm, then try to figure out what input you've given it. — paddy
In some cases, e.g. when starting or restarting, there is no prev. — user3386109
@paddy I have updated my post with an example input and output. — mjones

The Dark The Dark · Accepted Answer · 2016-01-26T01:50:50

Remember that you are going backward through the array. So this test

 S[n] > S[prev]

Should be the other way around:

 S[n] < S[prev]

I am not sure why you need prev at all, as it should always be n+1, so maybe use

if (S[n] == T[m] && n < 3 && S[n] < S[n+1])

If you need to make it work for any size, then either pass the size in, or just a flag to say don't check n+1

Edit:

My mistake - you want to be going through the first if case when n == 3 (or size), as you are at the start of a (potentially) increasing subsequence.

The if test should be

if (S[n] == T[m] && (n == 3 || S[n] < S[n+1]))

Note that this if test:

if (n == 0 || m  == 0)
    return 1;

is ignoring the first element of either sequence (and assuming it is at the end of an increasing subsequence). What is needed is to stop the recursion when you have gone before the start of either sequence. You also know that when you have gone before the start of the sequence, you can't possibly be in a subsequence, so you can return 0 for the length of the subsequence. So the test should be

if (n < 0 || m < 0)
    return 0;

Longest Common Increasing Subsequence Dynamic Programming

1 Answers