fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<string.h>
  4. using namespace std;
  5.  
  6. int a[5005];
  7. int b[5005];
  8. int path[5005];
  9. int prev[5005];
  10. int need[5005];
  11.  
  12.  
  13. int main()
  14. {
  15.     int x,y;
  16.  
  17.     memset(a,0, sizeof(a));
  18.     memset(b,0, sizeof(b));
  19.     scanf("%d",&x);
  20.     for(int i=0;i<x;i++)
  21.     {
  22.             scanf("%d",&a[i]);
  23.             }
  24.     scanf("%d",&y);
  25.     for(int i=0;i<y;i++)
  26.     {
  27.             scanf("%d",&b[i]);
  28.     }
  29.     for(int i=0;i<5005;i++)
  30.     {
  31.             path[i]=0;
  32.             prev[i]=-1;
  33.             }
  34.      int loc_pos=-1;
  35.      int temp=0;
  36.      int max=0;
  37.      int max_pos=-1;
  38.            for(int i=0;i<x;i++)
  39.            {
  40.                    temp=0;
  41.                    loc_pos=-1;
  42.                    for(int j=0;j<y;j++)
  43.                    {
  44.                            if((b[j]<a[i])&& temp<path[j])
  45.                            {
  46.                                  temp=path[j];
  47.                                  loc_pos=j;           
  48.                            }
  49.                            if(a[i]==b[j])
  50.                            {
  51.                               path[j]=temp+1; 
  52.                               prev[j]=loc_pos; 
  53.                               if(max<path[j])
  54.                            {
  55.                                max=path[j];
  56.                                max_pos=j;           
  57.                            }         
  58.                            }
  59.  
  60.                    }
  61.  
  62.            }
  63.            cout<<max<<endl;
  64.            int j=0;
  65.      while(max_pos!=-1)
  66.      {
  67.      	j++;
  68.      	need[j]=b[max_pos];
  69.      	max_pos=prev[max_pos];
  70.      }
  71.  
  72.      for(int i=j;i>0;i--)
  73.       {printf("%d ",need[i]);}
  74.            cout<<endl;
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
8
4 9 2 5 6 4 3 5 9
6
2 13 6 3 4 5 1
stdout
copy 
3
2 3 5
https://ideone.com/7iwGJg
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!