Get this book -> Problems on Array: For Interviews and Competitive Programming

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

- An increasing order sequence is considered Bitonic with the
**decreasing part as empty** - 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)**.