Hi,
Last week, one of our trainees attended Interview in RGS Construction Technologies in Chennai. They focus mainly on the logical thinking and ability of the candidates. It is a good approach to find out good programmers. One Interview question asked there to find out Longest Bitonic Subsequence.
Hope you understand the below program. Comments are added then and there in the program itself to understand clearly. For time being, it is taken from geeksforgeeks, as they have similar, straight forward question in their portal.
class LongestBitonicSubsequence
{
/* lbs() returns the length of the Longest Bitonic Subsequence in
arr[] of size n. The function mainly creates two temporary arrays
lis[] and lds[] and returns the maximum lis[i] + lds[i] – 1.
lis[i] ==> Longest Increasing subsequence ending with arr[i]
lds[i] ==> Longest decreasing subsequence starting with arr[i]
*/
static int lbs( int arr[], int n )
{
int i, j;
/* Allocate memory for LIS[] and initialize LIS values as 1 for
all indexes */
int[] lis = new int[n];
for (i = 0; i < n; i++)
lis[i] = 1;
/* Compute LIS values from left to right */
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
/* Allocate memory for lds and initialize LDS values for
all indexes */
int[] lds = new int [n];
for (i = 0; i < n; i++)
lds[i] = 1;
/* Compute LDS values from right to left */
for (i = n-2; i >= 0; i–)
for (j = n-1; j > i; j–)
if (arr[i] > arr[j] && lds[i] < lds[j] + 1)
lds[i] = lds[j] + 1;
/* Return the maximum value of lis[i] + lds[i] – 1*/
int max = lis[0] + lds[0] – 1;
for (i = 1; i < n; i++)
if (lis[i] + lds[i] – 1 > max)
max = lis[i] + lds[i] – 1;
return max;
}
public static void main (String[] args)
{
int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5,
13, 3, 11, 7, 15};
int n = arr.length;
System.out.println(“Length of LBS is “+ lbs( arr, n ));
}
}