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;

}