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
– paddy, Commented Jan 26, 2016 at 1:34
In some cases, e.g. when starting or restarting, there is no prev. — user3386109
– user3386109, Commented Jan 26, 2016 at 1:36
@paddy I have updated my post with an example input and output. — mjones
– mjones, Commented Jan 26, 2016 at 1:40

The Dark · Accepted Answer · 2016-01-26 07:45:07Z

1

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;

edited Jan 26, 2016 at 7:45

answered Jan 26, 2016 at 1:50

The Dark

8,5041 gold badge18 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

mjones Over a year ago

Wow you're so right about the prev variable, I was over thinking it. Your suggestion seems to work. Just to clarify, I would check for n < size?

mjones Over a year ago

Another consideration: would this solution work if the sequences are of different size?

The Dark Over a year ago

n < size should work fine. I think the idea should work for sequences of different sizes as you recurse through every option. However, I think you have a problem with your end condition, if both sequences are the same, I think you end up with size + 1 (maybe test a few more sequences).

mjones Over a year ago

Hmm you seem to be right. After testing, now matter which two sequences I give it, if they are the same, the output is two. I'm still failing to see how my end condition is causing this. Can you clarify what you mean by you end up with size + 1? Thanks

The Dark Over a year ago

Oops - I meant size - 1 (i.e. 3 for both sequences being 1,2,3,4). I'll update my answer with some new info.

|

Collectives™ on Stack Overflow

Longest Common Increasing Subsequence Dynamic Programming

1 Answer 1

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related