Given an array arr[0 … n-1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing. Write a function that takes an array as argument and returns the length of the longest bitonic subsequence.

**Solution:**
int lbs(int *arr, int len)

{

if(arr == NULL || len == 0)

return 0;

int *lis = new int[len];

for(int i = 0; i < len; ++i)

lis[i] = 1;

for(int i = 1; i < len; ++i)

{

for(int j = 0; j < i; ++j)

{

if(arr[i] > arr[j] && lis[i] < lis[j] + 1)

lis[i] = lis[j] + 1;

}

}

int *lds = new int[len];

for(int i = 0; i < len; ++i)

lds[i] = 1;

for(int i = len-2; i >= 0; --i)

{

for(int j = len-1; j > i; --j)

{

if(arr[i] > arr[j] && lds[i] < lds[j] + 1)

lds[i] = lds[j] + 1;

}

}

int max = lis[0] + lds[0] - 1;

for(int i = 1; i < len; ++i)

{

if(max < lis[i] + lds[i] - 1)

max = lis[i] + lds[i] - 1;

}

return max;

}

## No comments:

## Post a Comment