Wednesday, November 26, 2014

Pubmatic Question: Longest Bitonic subsequence

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