fork(7) download
  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
stdin
Standard input is empty
stdout
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