Longest Bitonic Sequence

Reading time: 30 minutes | Coding time: 10 minutes

x1, x2, x3, ... xn
where:
    x1 < x2 < x3 < ... < xm
    xm > xm+1 > xm+2 > ... > xn

10, 25, 36, 40, 59, 48, 34, 20, 5

Here the sequence first increases from 10 to 59 then descreases to 5.

EXAMPLES:-

arr[] = {1, 11, 2, 10, 4, 5, 2, 1}
 the longest bitonic sequence is 1, 2, 4, 5, 2, 1 of length 6.
arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
The  longest bitonic sequence is 0, 8, 12, 14, 13, 11, 7 of length 7.

Note that a bitoic sequence starting from a value reaches a peak value in a strict increasing order of values. Then it start decreasing monotonically. So, we can easily perceive that a bitonic sequence consists of a increasing subsequence and a decreasing subsequence. So, a longest bitonic subsequence would be subsequence that consists of a longest increasing subsequence (LIS) ending at peak and a longest decreasing subsequence (LDS) starting at peak.

So, 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.
    We need to find the **position i with maximum value** of LIS[i]+LDS[i]-1.

In order to find solution of biotonic sunsequence we can use the complete logic of Longest Increasing Subsequence, You can see previous article on longest increasing subsequence of better understanding.

Example walk-through

Let us take an example:

arr[]= {1,11,2,10,4,5,2,1}

for this we need to find two new array LIS[] (longest increasing subsequence) and LDS[] (longest decreasing subsequence)

For LIS[i]:-

LIS[0] = {1}
LIS[i] = {Max(LIS[j])} + 1 where j < i and arr[j] < arr[i] 
          = arr[i], if there is no such j

Initial value:-

LIS[]:-

Final value:-

LIS[]:-

For LDS[]:-

LDS[n] = {1}
LDS[i] = 1+ {Max(LDS[j])} where j > i and arr[j] < arr[i] 
       = arr[i], if there is no such j

Here, we used the method of finding LIS[] in reverse order, Let us see how

Algorithm

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

Step 1:-

LDS[]:-

Step 2:-

LDS[]:-

LDS[]:-

Step 3:-

LDS[]:-

LDS[]:-

LDS[]

Similarily, we can repeat the procedure for rest value of LDS[i] and get a final result as shown:-

LDS[]:-

Our final value in list is given as:-

LIS[]

LDS[]

LIS[]+LDS[]-1

Final value in finding biotonic sequence can be given as:-

Input: {1,11,2,10,4,5,2,1}
Output: 6

LIS[]+LDS[]-1

Longest Bitonic Subsequence is of length 6.

Below is c++ implementation of above idea:-

        #include<iostream>
        using namespace std; 
        // Utility function to print Longest Bitonic 
        // Subsequence 
           void print(vector<int>& arr, int size) 
        { 
          for(int i = 0; i < size; i++) 
          cout << arr[i] << " "; 
        } 
        // Function to construct and print Longest 
        // Bitonic Subsequence 
        void printLBS(int arr[], int n) 
        { 
        // LIS[i] stores the length of the longest 
        // increasing subsequence ending with arr[i] 
       vector<vector<int>> LIS(n);  
       // initialize LIS[0] to arr[0] 
       LIS[0].push_back(arr[0]); 
       // Compute LIS values from left to right 
       for (int i = 1; i < n; i++) 
       { 
         // for every j less than i 
         for (int j = 0; j < i; j++) 
         { 
            if ((arr[j] < arr[i]) && 
                (LIS[j].size() > LIS[i].size())) 
                LIS[i] = LIS[j]; 
         } 
         LIS[i].push_back(arr[i]); 
         } 
        /* LIS[i] now stores Maximum Increasing 
         Subsequence of arr[0..i] that ends with 
         arr[i] */
        // LDS[i] stores the length of the longest 
        // decreasing subsequence starting with arr[i] 
        vector<vector<int>> LDS(n); 
        // initialize LDS[n-1] to arr[n-1] 
        LDS[n - 1].push_back(arr[n - 1]);
        // Compute LDS values from right to left 
         for (int i = n - 2; i >= 0; i--) 
         { 
         // for every j greater than i 
         for (int j = n - 1; j > i; j--) 
         { 
            if ((arr[j] < arr[i]) && 
                (LDS[j].size() > LDS[i].size())) 
                LDS[i] = LDS[j]; 
         } 
          LDS[i].push_back(arr[i]); 
         } 
         // reverse as vector as we're inserting at end 
         for (int i = 0; i < n; i++) 
          reverse(LDS[i].begin(), LDS[i].end()); 
          /* LDS[i] now stores Maximum Decreasing Subsequence 
         of arr[i..n] that starts with arr[i] */
         int max = 0; 
         int maxIndex = -1; 
         for (int i = 0; i < n; i++) 
         { 
          // Find maximum value of size of LIS[i] + size 
          // of LDS[i] - 1 
          if (LIS[i].size() + LDS[i].size() - 1 > max) 
         { 
            max = LIS[i].size() + LDS[i].size() - 1; 
            maxIndex = i; 
         } 
         }  
         // print all but last element of LIS[maxIndex] vector 
        print(LIS[maxIndex], LIS[maxIndex].size() - 1); 
       // print all elements of LDS[maxIndex] vector 
       print(LDS[maxIndex], LDS[maxIndex].size()); 
        } 
        // Driver program 
         int main() 
         { 
         int arr[] = { 1, 11, 2, 10, 4, 5, 2, 1 }; 
         int n = sizeof(arr) / sizeof(arr[0]); 
          printLBS(arr, n); 
         return 0; 
          } 

Output:

  1 11 10 5 2 1

Complexity

Time complexity of above Dynamic Programming solution is O(n^2).
Auxiliary space used by the program is O(n^2).