Longest Bitonic Subsequence

November 24, 2021

Longest Bitonic Subsequence

The longest bitonic subsequence is a variation of the very famous problem – Longest Increasing subsequence. In this article we provide a C++ solution with explanation of the problem.

Longest Bitonic Subsequence Problem Description

A sequence is called bitonic if it has two parts – the first part is sorted in increasing order and the second part is sorted in decreasing order.

Eg. 1 2 3 2 1

An increasing sequence is also bitonic (with decreasing part empty) & similarly a decreasing sequence is also bitonic (with increasing part empty).

Given n integers find the length of longest bitonic subsequence in the array.

Input:

First-line contains integer n – the length of the array.
The next Line contains n integers.

Output:

Single Integer, the required length.

Longest Bitonic Subsequence Solution

This problem is a variation of longest increasing subsequence problem.

To understand solution for this problem think anout finding the length of longest bitonic subsequence for a single element i such that it forms the peak in the sequence. What will be the length?

longest length Bitonic for i = (length of longest increasing subsequence ending at i) + (length of longest decreasing subsequence starting at i – 1).

Important Points

We subtracted 1 because element i is counted twice.
To find the length of longest deceasing subsequence we apply similar algorithm as applied in LIS but in reverse.

Now we just have to find the length for for all elements of the array and return the maximum.

Time Complexity – O(n^2)

Space Complexity – O(n)

Code

#include <bits/stdc++.h>
using namespace std;
int bitonic(int arr[], int n)
{
    int lis[n]; // Length of largest increasing subsequence ending at i
    int lds[n]; // Length of largest decreasing subsequence starting at i
    int ans = 0;

    /*
        For lis we check all elements left of i
    */
    for (int i = 0; i < n; i++)
    {
        lis[i] = 1;
        for (int j = 0; j < i; j++)
            if (arr[j] <= arr[i])
                lis[i] = max(lis[i], 1 + lis[j]);
    }

    /*
        for lds we check all elements right of i
    */

    for (int i = n – 1; i >= 0; i–)
    {
        lds[i] = 1;
        for (int j = n – 1; j > i; j–)
            if (arr[i] >= arr[j])
                lds[i] = max(lds[i], 1 + lds[j]);
    }

    /*
        Bitonic subsequence of any element i = lis[i] + lds[i] – 1
        -1 because element i is counted twice
    */
    for (int i = 0; i < n; i++)
    {
        ans = max(ans, lds[i] + lis[i] – 1);
    }
    return ans;
}
int main()
{
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << bitonic(arr, n) << endl;
    return 0;
}

Output

7
1 2 1 3 1 2 1
5
Explanation - 1 2 3 2 1 or 1 2 1 1 1 are required sub sequences.