Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
1.1.
Problem statement
1.2.
Sample Examples
2.
Approach
3.
Implementation in C++
3.1.
Complexity Analysis
4.
Frequently Asked Questions
5.
Key Takeaways
Last Updated: Mar 27, 2024

Longest Bitonic Subsequence

Author Sandeep kamila
2 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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 10 22 9 33 21 50 41 60 80 3
Longest length 1 2 1 3 2 4 4 5 6 1
Increasing subsequences 10

10

22

9

10

22

33

10

21

10

22

33

50

10

22

33

41

10

22

33

50

60

10

22

33

50

60

80

3

 

Longest decreasing subsequence:

Given array 10 22 9 33 21 50 41 60 80 3
Longest length 3 3 2 3 2 3 2 2 2 1
Decreasing subsequences

10

9

3

22

9

3

9

3

33

21

3

21

3

50

41

3

41

3

60

3

 

80

3

 

3

 

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 }
 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

 

Output:

7

 

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!

Previous article
Classy Numbers
Next article
Maximise Difference Between Sum Of Even And Odd-Indexed Elements Of A Subsequence
Live masterclass