Set 15 (Longest Bitonic Subsequence) | GeeksforGeeks

Dynamic Programming | Set 15 (Longest Bitonic Subsequence) | GeeksforGeeks
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.

This problem is a variation of standard Longest Increasing Subsequence (LIS) problem. Let the input array be arr[] of length n. We need to construct two arrays lis[] and lds[] using Dynamic Programming solution of LIS problem. lis[i] stores the length of the Longest Increasing subsequence ending with arr[i]. lds[i] stores the length of the longest Decreasing subsequence starting from arr[i]. Finally, we need to return the max value of lis[i] + lds[i] – 1 where i is from 0 to n-1.
Time Complexity: O(n^2) Auxiliary Space: O(n)

/* 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]

*/

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;

}

O(nlongn)
https://www.geeksforgeeks.org/longest-bitonic-subsequence-onlogn/

The idea is to follow Longest Increasing Subsequence Size (n log n) to see the way length of Longest Increasing subsequence (LIS) is calculated.

Algorithm:

Step 1: Define 4 Auxiliary arrays of size n:
        increasing[n] to calculate LIS of the 
        array  tail1[n] to store the values for 
        LIS for increasing[n]
        decreasing[n] to calculate LIS of the 
        array  tail2[n] to store the values for
        LIS for decreasing[n]
Step 2: Find LIS for increasing array
Step 3: Reverse array and store it in decreasing
Step 4: Find LIS for decreasing array
Step 5: Longest Bitonicc SubSequence length now 
        will be max of tail1[i] + tail2[i] + 1

http://ideone.com/LGx705
http://dotnetvisio.blogspot.com/2013/07/bitonic-subsequence-problem.html

    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;
    }

http://www.zrzahid.com/longest-bitonic-sequence/

the longest bitonic subsequence with peak at a position i would consists of longest increasing subsequence that ends at i and a longest decreasing subsequence starting at i. We need to construct two arrays LIS[] and LDS[] such that for each position i –

 LIS[i] : length of the Longest Increasing subsequence ending at arr[i]. 
 LDS[i]:  length of the longest Decreasing subsequence starting from arr[i].         
        LIS[i]+LDS[i]-1 : the length Longest Bitonic Subsequence with peak at i.

the LIS problem has an optimal substructure LIS(i) = max{1+LIS(j)} for all j < i 
Longest Decreasing Subsequence (LDS) can be computed similar to LIS with the recurrence relation LDS(i) = max{1+LDS(j)} for all j < i and A[j] > A[i] 

public static int longestBiotonicSequence(int[] a){
 int[] lis = new int[a.length];
 int[] lds = new int[a.length];
 //base cases - single number is a lis and lds
 Arrays.fill(lis, 1);
 Arrays.fill(lds, 1);
 int maxBiotonicLen = Integer.MIN_VALUE;
 
 //longest increasing subsequence
 //lis(i) = max{1+lis(j)}, for all j < i and a[j] < a[i]
 for(int i = 1; i < a.length; i++){
  for(int j = 0; j < i; j++){
   if(a[i] > a[j] && lis[j] + 1 > lis[i]){
    lis[i] = lis[j]+1;
   }
  }
 }
 
 //longest decreasing subsequence
 //lds(i) = max{1+lds(j)}, for all j < i and a[j] > a[i]
 //longest biotonic seq lbs(i) = lis(i)+lds(i)-1
 maxBiotonicLen = lis[0]+lds[0]-1;
 for(int i = 1; i < a.length; i++){ // seems not right
  for(int j = 0; j < i; j++){
   if(a[i] < a[j] && lds[j] + 1 > lds[i]){
    lds[i] = lds[j]+1;
   }
  }
  maxBiotonicLen = Math.max(maxBiotonicLen, lis[i]+lds[i]-1);
 }
 
 return maxBiotonicLen;
}

http://www.geeksforgeeks.org/printing-longest-bitonic-subsequence/
Printing Longest Bitonic Subsequence
Read full article from Dynamic Programming | Set 15 (Longest Bitonic Subsequence) | GeeksforGeeks