fork(7) download
copy 
  1. #include<stdio.h>
  2. #include<limits.h>
  3.  
  4. int max(int a,int b)
  5. {
  6.     return(a > b?a:b);
  7. }
  8.  
  9. void revArrCpy(int a[],int b[],int n)
  10. {
  11.     int i;
  12.     for(i = 0;i < n;i++)
  13.     b[n-i-1] = a[i];
  14. }
  15.  
  16. int binSearchIndex(int a[],int low,int high,int x)
  17. {
  18.     while(low < high)
  19.     {
  20.         int mid = low + (high - low)/2;
  21.         if(a[mid] < x)
  22.         low = mid+1;
  23.         else if(a[mid] > x)
  24.         high = mid;
  25.         else
  26.         return mid;
  27.     }
  28.  
  29.     return low;
  30. }
  31.  
  32. void getLISArray(int a[],int lis[],int n)
  33. {
  34.     int i = 0,end[n];
  35.  
  36.     end[i] = a[0];
  37.     int len = 0;
  38.     lis[i] = len+1;
  39.  
  40.     for(i = 1;i < n;i++)
  41.     {
  42.         if(a[i] <= end[len])
  43.         {
  44.             int pos = binSearchIndex(end,0,len,a[i]);
  45.             lis[i] = pos+1;
  46.             end[pos] = a[i];
  47.         }
  48.         else{
  49.             end[++len] = a[i];
  50.             lis[i] = len+1;
  51.         }
  52.     }
  53. }
  54.  
  55. void swap(int* a,int* b)
  56. {
  57.     int temp = *a;
  58.     *a = *b;
  59.     *b = temp;
  60. }
  61.  
  62. void reverse(int a[],int n)
  63. {
  64.     int low = 0,high = n-1;
  65.     while(low < high)
  66.     {
  67.         swap(a+low,a+high);
  68.         low++;
  69.         high--;
  70.     }
  71. }
  72.  
  73. void printArray(int a[],int n)
  74. {
  75.     int i;
  76.     for(i = 0;i < n;i++)
  77.     printf("%d ",a[i]);
  78.     printf("\n");
  79. }
  80.  
  81. int lbs(int a[],int n)
  82. {
  83.     int lis[n],lds[n],i;
  84.     for(i = 0;i < n;i++)
  85.     lis[i] = lds[i] = 1;
  86.  
  87.     getLISArray(a,lis,n);
  88.     printArray(lis,n);
  89.     int rev[n];
  90.     revArrCpy(a,rev,n);
  91.     getLISArray(rev,lds,n);
  92.     reverse(lds,n);
  93.     printArray(lds,n);
  94.  
  95.     int maximum = INT_MIN;
  96.     for(i = 0;i < n;i++)
  97.     maximum = max(maximum,lis[i]+lds[i]-1);
  98.  
  99.     return maximum;
  100. }
  101.  
  102. int main()
  103. {
  104.     int a[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
  105.     int n = sizeof(a)/sizeof(a[0]);
  106.     printf("The LBS is %d\n",lbs(a,n));
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0s 2296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 2 3 2 3 3 4 2 4 3 5 3 5 4 6 
1 4 3 5 2 4 3 4 1 3 2 3 1 2 1 1 
The LBS is 7
https://ideone.com/LGx705
language:
C (gcc 8.3)
created:
10 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!