The Longest Common Subsequence

#codeifyoucansolve
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences.

Given two sequence of integers, A=[a1,a2,…,an] and B=[b1,b2,…,bm], find any one longest common subsequence.

In case multiple solutions exist, print any of them. It is guaranteed that at least one non-empty common subsequence will exist.
Input Format

First line contains two space separated integers, n and m, where n is the size of sequence A, while m is size of sequence B. In next line there are n space separated integers representing sequence A, and in third line there are m space separated integers representing sequence B.

n m
A1 A2 … An
B1 B2 … Bm

Constraints

1≤n≤100
1≤m≤100
0≤ai<1000,where i∈[1,n]
0≤bj<1000,where j∈[1,m]

Output Format

Print the longest common subsequence and each element should be separated by at least one white-space. In case of multiple answers, print any one of them.

Sample Input

5 6
1 2 3 4 1
3 4 1 2 1 3

Sample Output

1 2 3

Explanation

There is no common subsequence with length larger than 3. And “1 2 3”, “1 2 1”, “3 4 1” are all correct answers.

Tested by Khongor

Copyright (c) 2015 HackerRank.
All Rights Reserved
Suggest Edits

Solved score: 49.50pts
1433 hackers have submitted code

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void lcs(int N,int M,int m[],int n[])
{
    int L[M+1][N+1],i,j,k;
    for(i=0;i<=M;i++)
        {
        for(j=0;j<=N;j++)
            {
            if(i==0 || j==0)
                L[i][j]=0;
            else if(m[i-1]==n[j-1])
                L[i][j]=1+L[i-1][j-1];
             else
                {
                if(L[i-1][j]>L[i][j-1])
                    {
                    L[i][j]=L[i-1][j];
                }
                else
                    {
                    L[i][j]=L[i][j-1];
                }
            }
        }
    }
    k=L[M][N];
    int l[k];
    i=M;j=N;
    while(i>0&&j>0)
        {
        if(m[i-1]==n[j-1])
            {
         // printf("%d ",m[i-1]);
            l[k-1]=m[i-1];
            i--;j--;k--;
        }
        else if(L[i-1][j]>L[i][j-1])
            i--;
        else
            j--;
    }
    for(i=0;i<L[M][N];i++)
       printf("%d ",l[i]); 
    printf("\n");
}
int main() {

    int N,M,m[100],n[100];
    int i,j;
    scanf("%d%d",&N,&M);
    for(i=0;i<N;i++)
        scanf("%d",&n[i]);
    for(i=0;i<M;i++)
        scanf("%d",&m[i]);
    lcs(N,M,n,m);
    return 0;
}

Compiled :
http://ideone.com/F2Rgoy