The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). Note that subsequence is different from a substring, see substring vs. 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.
A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.
A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.
Examples:
Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
Output: 6(A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)
Output: 6(A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)
Input arr[] = {12, 11, 40, 5, 3, 1}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)
Input arr[] = {80, 60, 30, 40, 20, 10}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)
Program in C#
**************************************************************
class Bitonic { private static int Maximum(int []arr,int size) { int []bc=new int[size]; int i,j,max=1; bc[0]=1; for(i=1;i<size;i++) { bc[i]=1; for(j=i-1;j>=0;j--) { if((bc[i]<bc[j]+1) && arr[i]>arr[j]) { bc[i]=bc[j]+1; } }
if(bc[i]>max)
{
max=bc[i];
} } bc[size-1]=1; for(i=size-2;i>=0;i--) { int prv=bc[i]; bc[i]=1; for(j=i+1;j<size;j++) { if((bc[i]<bc[j]+1) && arr[i] > arr[j]) { bc[i]=bc[j]+1; } } if(prv+bc[i]-1 > max) { max=prv+bc[i]-1; } } return max; }
public static int GetMaxLength(int []array) { return Maximum(array,array.Length); } }
class Program{ public static void Main(string[] args){
int len=Bitonic.GetMaxLength(new int[]{80, 60, 30, 40, 20, 10});
}
}
Thats it , This is the logic for bitonic subsequence
dynamic programming approach here. For sake of simplicity , assume we need to find only the maximal length of such sequence.
No comments:
Post a Comment