Cod sursa(job #2177660)

Utilizator CojocaruDragosCojocaru Dragos Andrei CojocaruDragos Data 18 martie 2018 18:58:47
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;
ifstream in("cmlsc.in");
ofstream out("cmlsc.out");
int a[1025],b[1025],sol[1025];
int mat[1025][1025];
int i,j,n,m,imax,nmax,lsol;
int main()
{
   in>>n>>m;

for(i=1;i<=n;i++)
    in>>a[i];
for(j=1;j<=n;j++)
    in>>b[j];
for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
       {
           if(a[i]==b[j])
            mat[i][j]=1+mat[i-1][j-1];
        else
            mat[i][j]=max(mat[i-1][j],mat[i][j-1]);
       }
i=n;j=m;
while(i!=0)
      {
          if(a[i]==b[j])
          {
              sol[++lsol]=a[i];
              i--;
              j--;
          }
          else
            if(mat[i-1][j]<mat[i][j-1])
            j--;

            else
                i--;

      }
for(i=lsol;i>=1;i--)
    out<<sol[i]<<" ";


    return 0;
}