Table of contents

Introduction

1.1.

Problem statement

1.2.

Sample Examples

Approach

Implementation in C++

3.1.

Complexity Analysis

Frequently Asked Questions

Key Takeaways

Last Updated: Mar 27, 2024

Longest Bitonic Subsequence

Q: Q1. What do you mean by a strictly increasing subsequence and a decreasing subsequence?

Ans: Numerous other subsequences can occur. When each term in a sequence is smaller than the term before it, the sequence is said to be "strictly increasing." When each term in a sequence is greater than the term after it, the sequence is said to be "strictly decreasing."

Q: Q2. How do you sort a bitonic array?

Ans: We compare the first half's first element to the first half's second element, then the second half's second element to the second half's second element, and so on. If one of the first half's elements is smaller, we swap them. We receive two bitonic sequences in the array after comparing and exchanging procedures.

Q: Q3. How do you determine which subsequence is the longest?

Ans: The length of the longest common subsequence is represented by the value in the last row and column. Start with the last element and follow the arrow's direction to discover the longest common subsequence. The longest common subsequence is formed by the items corresponding to the () sign.

Q: Q4. What is the application of the longest common subsequence?

Ans: The longest common subsequence problem is a basic computer science problem used in computational linguistics and bioinformatics. It is the foundation of data comparison algorithms like the diff utility.

Author Sandeep Kamila

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

Problem statement

We are given an array of size N. Our task is to find the length of the Longest Bitonic Subsequence present in the given array.

Bitonic Subsequence: A subsequence that is first increasing and then decreasing.

An ascending order sequence is also considered bitonic, with the decreasing part as empty.
A descending order sequence is also considered bitonic, with the increasing part as empty.

Sample Examples

Example 1:

Input: a[] = { 7, 9, 5, 10, 13, 2, 3, 6 }
Output: 5

Explanation
Longest Bitonic Subsequence: {7, 9, 10, 13, 6}

Example 2:

Input: a[]= { 10, 22, 9, 33, 21, 50, 41, 60, 80, 3 }
Output: 7

Explanation
Longest Bitonic Subsequence: { 10, 22, 33, 50, 60, 80, 3 }

Approach

This is a standard dynamic programming problem variation, the Longest increasing subsequence (LIS). A bitonic sequence is first increasing and then decreasing sequence.

We first calculate the length of all the longest increasing subsequences ending with a[i] and decreasing subsequences starting with a[i] in the given array using dynamic programming.

The length of the longest bitonic subsequence in the given array:

Length of longest increasing subsequence at index (i) + Length of the longest decreasing subsequence at index (i) - 1, where i ranges from 0 to n-1.

Here, we are subtracting 1 as we are adding a[i] twice in our longest increasing and decreasing subsequence.

Let’s understand the above approach with an example:

Longest increasing subsequence:

Given array

Longest length

Increasing subsequences

Longest decreasing subsequence:

Given array

Longest length

Decreasing subsequences

If we consider the Increasing subsequence : {10, 22, 33, 50, 60, 80} of length 6 and the Decreasing subsequence: {80, 3} of length 2.

Max length = (6 + 2) - 1 = 7 // subtracting 1 because 80 is considered twice.

Longest Bitonic Subsequence obtained: { 10, 22, 33, 50, 60, 80, 3 }

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int longest_bitonic(int a[], int n)
{
	int LIS[n];

	for (int i = 0; i < n; i++)
		LIS[i] = 1;

	for (int i = 1; i < n; i++)
		for (int j = 0; j < i; j++)
			if (a[i] > a[j] && LIS[i] < LIS[j] + 1)
				LIS[i] = LIS[j] + 1;

	int LDS[n];

	for (int i = 0; i < n; i++)
		LDS[i] = 1;

	for (int i = n - 2; i >= 0; i--)
		for (int j = n - 1; j > i; j--)
			if (a[i] > a[j] && LDS[i] < LDS[j] + 1)
				LDS[i] = LDS[j] + 1;

	int max_length = LIS[0] + LDS[0] - 1;

	for (int i = 1; i < n; i++)
		if (LIS[i] + LDS[i] - 1 > max_length)
			max_length = LIS[i] + LDS[i] - 1;

	return max_length;
}

int main()
{
	int a[] = { 10, 22, 9, 33, 21, 50, 41, 60, 80, 3 };
	int n = sizeof(a) / sizeof(a[0]);

	cout << longest_bitonic(a, n) << endl;

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Complexity Analysis

Time complexity: O(N^2), as we are using two nested loops of size N, where N is the size of the array.

Space complexity: O(N), as we are using LIS[] and LDS[] array to store the length of the longest increasing and decreasing subsequences, respectively.

Check out this : Longest common subsequence

Frequently Asked Questions

Q1. What do you mean by a strictly increasing subsequence and a decreasing subsequence?

Ans: Numerous other subsequences can occur. When each term in a sequence is smaller than the term before it, the sequence is said to be "strictly increasing." When each term in a sequence is greater than the term after it, the sequence is said to be "strictly decreasing."

Q2. How do you sort a bitonic array?

Ans: We compare the first half's first element to the first half's second element, then the second half's second element to the second half's second element, and so on. If one of the first half's elements is smaller, we swap them. We receive two bitonic sequences in the array after comparing and exchanging procedures.

Q3. How do you determine which subsequence is the longest?

Ans: The length of the longest common subsequence is represented by the value in the last row and column. Start with the last element and follow the arrow's direction to discover the longest common subsequence. The longest common subsequence is formed by the items corresponding to the () sign.

Q4. What is the application of the longest common subsequence?

Ans: The longest common subsequence problem is a basic computer science problem used in computational linguistics and bioinformatics. It is the foundation of data comparison algorithms like the diff utility.

Key Takeaways

This article discussed the approach to finding the longest bitonic subsequence using the standard dynamic programming longest increasing subsequence problem with complete explanation and implementation in the C++ programming language.

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free!

Check out this problem - Longest Subarray With Sum K

Thank you for reading!