Longest Bitonic Sequence


Reading time: 30 minutes | Coding time: 10 minutes

The problem we will solve is given a sequence an array of positive integers and have to find the length of longest bitonic subsequence. Using dynamic programming ideas, we will solve this on O(N^2) time complexity

A bitonic sequence is a sequence which is first increasing to a peak value and then decreasing that is it is of the following form:

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

For example:

10, 25, 36, 40, 59, 48, 34, 20, 5
Here the sequence first increases from 10 to 59 then descreases to 5.

NOTE:-

  1. An increasing order sequence is considered Bitonic with the decreasing part as empty
  2. A decreasing order sequence is considered Bitonic with the increasing part as empty.

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.

t1

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[]:-

array 1 11 2 10 4 5 2 1
value 1 1 1 1 1 1 1 1

Final value:-

LIS[]:-

array 1 11 2 10 4 5 2 1
value 1 2 2 3 3 4 2 1

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[]:-

index 1 2 3 4 5 6 i=7 j=8
array 1 11 2 10 4 5 2 1
value 1 1 1 1 1 1 1 1

Step 2:-

LDS[]:-

index 1 2 3 4 5 i=6 7 j=8
array 1 11 2 10 4 5 2 1
value 1 1 1 1 1 1 2 1

LDS[]:-

index 1 2 3 4 5 i=6 j=7 8
array 1 11 2 10 4 5 2 1
value 1 1 1 1 1 2 2 1

Step 3:-

LDS[]:-

index 1 2 3 4 i=5 6 7 j=8
array 1 11 2 10 4 5 2 1
value 1 1 1 1 1 3 2 1

LDS[]:-

index 1 2 3 4 i=5 6 j=7 8
array 1 11 2 10 4 5 2 1
values 1 1 1 1 2 3 2 1

LDS[]

index 1 2 3 4 i=5 j=6 7 8
array 1 11 2 10 4 5 2 1
value 1 1 1 1 3 3 2 1

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

LDS[]:-

array 1 11 2 10 4 5 2 1
value 1 5 2 4 3 3 2 1

Our final value in list is given as:-

LIS[]

array 1 11 2 10 4 5 2 1
value 1 2 2 3 3 4 2 1

LDS[]

array 1 11 2 10 4 5 2 1
value 1 5 2 4 3 3 2 1

LIS[]+LDS[]-1

array 1 11 2 10 4 5 2 1
value 1 6 3 6 5 6 3 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

array 1 11 2 10 4 5 2 1
value 1 *6* 3 *6* 5 *6* 3 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).