# Longest Bitonic Sequence

#### Dynamic Programming (DP) Algorithms

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.

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).

#### Tanya Anand

Final Year Undergrad (2020) | CSE | NIT Hamirpur | Intern at OpenGenus