Advertisement
naeem043

C DP LIS(Longest increasing Sub sequence)

Jul 13th, 2018
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.96 KB | None | 0 0
  1. #include<stdio.h>
  2. int l[11],a[11],par[11],seq[11];
  3.  
  4. int parent(int n)
  5. {
  6.    int x;
  7.    if(n!=0) return 0;
  8.    seq[n] = parent(n);
  9.    return seq[n];
  10. }
  11.  
  12.  
  13. int main()
  14. {
  15.     int j,i;
  16.  
  17.     a[1] = 9;
  18.     a[2] = 2;
  19.     a[3] = 5;
  20.     a[4] = 3;
  21.     a[5] = 7;
  22.     a[6] = 11;
  23.     a[7] = 8;
  24.     a[8] = 10;
  25.     a[9] = 13;
  26.     a[10] = 6;
  27.  
  28.     l[0] = 0;
  29.  
  30.     for(i=1;i<11;i++)
  31.     {
  32.         for(j=0;j<i;j++)
  33.         {
  34.             if(a[j] < a[i])
  35.             {
  36.                 l[i] = 1 + l[j];
  37.                 par[i] = j;
  38.                 seq[i] = a[i-1];
  39.             }
  40.          }
  41.     }
  42.  
  43.     printf("Array:    ");
  44.      for(i=1;i<11;i++)
  45.         printf("%d\t",a[i]);
  46.  
  47.     printf("\nLength:   ");
  48.      for(i=1;i<11;i++)
  49.         printf("%d\t",l[i]);
  50.  
  51.      printf("\nParents:  ");
  52.      for(i=1;i<11;i++)
  53.         printf("%d\t",par[i]);
  54.  
  55.      printf("\nSequence: ");
  56.       for(i=5;i>=1;i--)
  57.            printf("%d\t",seq[i]);
  58.  
  59.  
  60.  
  61.  
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement