The Longest Common Subsequence (LCS) Discussions | Tutorials | HackerRank
  • + 1 comment
    #include <cmath>
    #include <cstdio>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    
    int main() {
        int n,m;
        cin>>n>>m;
        int multi[n+1][m+1],tracker[n+1][m+1];
        int ar[n],arr[m];
        for(int i=0;i<n;i++)
        cin>>ar[i];
        for(int j=0;j<m;j++)
        cin>>arr[j];
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                if(i==0||j==0)
                multi[i][j] = 0;
                else
                {
                    if(ar[i-1] == arr[j-1])
                    {
                    multi[i][j] = multi[i-1][j-1]+1;
                    tracker[i][j] = 3;
                    }
                    else
                    {
                    multi[i][j] = max(multi[i-1][j],multi[i][j-1]);
                    if(multi[i][j] == multi[i-1][j])
                    tracker[i][j] = 1;
                    else
                    tracker[i][j] = 2;
                    }
                }
            }
        }
        
        int j = m;
        vector<int> ans;
    
        for(int i=n;i>0;i--)
        {
            if(j<=0)
            break;
            if(tracker[i][j] == 1)
            {
                continue;
            }
    
            else if(tracker[i][j] == 2)
            {
                i++;
                j--;
            }
    
            else if(tracker[i][j] == 3)
            {
                j--;
                ans.push_back(arr[j]);
            }
        }
    
        for(int i=ans.size()-1;i>=0;i--)
        {
            cout<<ans[i]<<" ";
        }
    
    
    
        return 0;
    }