#include<stdio.h>
#include<limits.h>
int max(int a,int b)
{
return(a > b?a:b);
}
void revArrCpy(int a[],int b[],int n)
{
int i;
for(i = 0;i < n;i++)
b[n-i-1] = a[i];
}
int binSearchIndex(int a[],int low,int high,int x)
{
while(low < high)
{
int mid = low + (high - low)/2;
if(a[mid] < x)
low = mid+1;
else if(a[mid] > x)
high = mid;
else
return mid;
}
return low;
}
void getLISArray(int a[],int lis[],int n)
{
int i = 0,end[n];
end[i] = a[0];
int len = 0;
lis[i] = len+1;
for(i = 1;i < n;i++)
{
if(a[i] <= end[len])
{
int pos = binSearchIndex(end,0,len,a[i]);
lis[i] = pos+1;
end[pos] = a[i];
}
else{
end[++len] = a[i];
lis[i] = len+1;
}
}
}
void swap(int* a,int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void reverse(int a[],int n)
{
int low = 0,high = n-1;
while(low < high)
{
swap(a+low,a+high);
low++;
high--;
}
}
void printArray(int a[],int n)
{
int i;
for(i = 0;i < n;i++)
}
int lbs(int a[],int n)
{
int lis[n],lds[n],i;
for(i = 0;i < n;i++)
lis[i] = lds[i] = 1;
getLISArray(a,lis,n);
printArray(lis,n);
int rev[n];
revArrCpy(a,rev,n);
getLISArray(rev,lds,n);
reverse(lds,n);
printArray(lds,n);
int maximum = INT_MIN;
for(i = 0;i < n;i++)
maximum = max(maximum,lis[i]+lds[i]-1);
return maximum;
}
int main()
{
int a[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
int n = sizeof(a)/sizeof(a[0]);
printf("The LBS is %d\n",lbs
(a
,n
)); return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bGltaXRzLmg+CgppbnQgbWF4KGludCBhLGludCBiKQp7CiAgICByZXR1cm4oYSA+IGI/YTpiKTsKfQoKdm9pZCByZXZBcnJDcHkoaW50IGFbXSxpbnQgYltdLGludCBuKQp7CiAgICBpbnQgaTsKICAgIGZvcihpID0gMDtpIDwgbjtpKyspCiAgICBiW24taS0xXSA9IGFbaV07Cn0KCmludCBiaW5TZWFyY2hJbmRleChpbnQgYVtdLGludCBsb3csaW50IGhpZ2gsaW50IHgpCnsKICAgIHdoaWxlKGxvdyA8IGhpZ2gpCiAgICB7CiAgICAgICAgaW50IG1pZCA9IGxvdyArIChoaWdoIC0gbG93KS8yOwogICAgICAgIGlmKGFbbWlkXSA8IHgpCiAgICAgICAgbG93ID0gbWlkKzE7CiAgICAgICAgZWxzZSBpZihhW21pZF0gPiB4KQogICAgICAgIGhpZ2ggPSBtaWQ7CiAgICAgICAgZWxzZQogICAgICAgIHJldHVybiBtaWQ7CiAgICB9CgogICAgcmV0dXJuIGxvdzsKfQoKdm9pZCBnZXRMSVNBcnJheShpbnQgYVtdLGludCBsaXNbXSxpbnQgbikKewogICAgaW50IGkgPSAwLGVuZFtuXTsKCiAgICBlbmRbaV0gPSBhWzBdOwogICAgaW50IGxlbiA9IDA7CiAgICBsaXNbaV0gPSBsZW4rMTsKCiAgICBmb3IoaSA9IDE7aSA8IG47aSsrKQogICAgewogICAgICAgIGlmKGFbaV0gPD0gZW5kW2xlbl0pCiAgICAgICAgewogICAgICAgICAgICBpbnQgcG9zID0gYmluU2VhcmNoSW5kZXgoZW5kLDAsbGVuLGFbaV0pOwogICAgICAgICAgICBsaXNbaV0gPSBwb3MrMTsKICAgICAgICAgICAgZW5kW3Bvc10gPSBhW2ldOwogICAgICAgIH0KICAgICAgICBlbHNlewogICAgICAgICAgICBlbmRbKytsZW5dID0gYVtpXTsKICAgICAgICAgICAgbGlzW2ldID0gbGVuKzE7CiAgICAgICAgfQogICAgfQp9Cgp2b2lkIHN3YXAoaW50KiBhLGludCogYikKewogICAgaW50IHRlbXAgPSAqYTsKICAgICphID0gKmI7CiAgICAqYiA9IHRlbXA7Cn0KCnZvaWQgcmV2ZXJzZShpbnQgYVtdLGludCBuKQp7CiAgICBpbnQgbG93ID0gMCxoaWdoID0gbi0xOwogICAgd2hpbGUobG93IDwgaGlnaCkKICAgIHsKICAgICAgICBzd2FwKGErbG93LGEraGlnaCk7CiAgICAgICAgbG93Kys7CiAgICAgICAgaGlnaC0tOwogICAgfQp9Cgp2b2lkIHByaW50QXJyYXkoaW50IGFbXSxpbnQgbikKewogICAgaW50IGk7CiAgICBmb3IoaSA9IDA7aSA8IG47aSsrKQogICAgcHJpbnRmKCIlZCAiLGFbaV0pOwogICAgcHJpbnRmKCJcbiIpOwp9CgppbnQgbGJzKGludCBhW10saW50IG4pCnsKICAgIGludCBsaXNbbl0sbGRzW25dLGk7CiAgICBmb3IoaSA9IDA7aSA8IG47aSsrKQogICAgbGlzW2ldID0gbGRzW2ldID0gMTsKCiAgICBnZXRMSVNBcnJheShhLGxpcyxuKTsKICAgIHByaW50QXJyYXkobGlzLG4pOwogICAgaW50IHJldltuXTsKICAgIHJldkFyckNweShhLHJldixuKTsKICAgIGdldExJU0FycmF5KHJldixsZHMsbik7CiAgICByZXZlcnNlKGxkcyxuKTsKICAgIHByaW50QXJyYXkobGRzLG4pOwoKICAgIGludCBtYXhpbXVtID0gSU5UX01JTjsKICAgIGZvcihpID0gMDtpIDwgbjtpKyspCiAgICBtYXhpbXVtID0gbWF4KG1heGltdW0sbGlzW2ldK2xkc1tpXS0xKTsKCiAgICByZXR1cm4gbWF4aW11bTsKfQoKaW50IG1haW4oKQp7CiAgICBpbnQgYVtdID0gezAsIDgsIDQsIDEyLCAyLCAxMCwgNiwgMTQsIDEsIDksIDUsIDEzLCAzLCAxMSwgNywgMTV9OwogICAgaW50IG4gPSBzaXplb2YoYSkvc2l6ZW9mKGFbMF0pOwogICAgcHJpbnRmKCJUaGUgTEJTIGlzICVkXG4iLGxicyhhLG4pKTsKICAgIHJldHVybiAwOwp9Cg==