The Longest Bitonic Subsequence problem is to find the longest subsequence of a given sequence such that it is first increasing and then decreasing. A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty. Examples:
Input: [1, 11, 2, 10, 4, 5, 2, 1]
Output: [1, 2, 10, 4, 2, 1] OR [1, 11, 10, 5, 2, 1]
OR [1, 2, 4, 5, 2, 1]
Input: [12, 11, 40, 5, 3, 1]
Output: [12, 11, 5, 3, 1] OR [12, 40, 5, 3, 1]
Input: [80, 60, 30, 40, 20, 10]
Output: [80, 60, 30, 20, 10] OR [80, 60, 40, 20, 10]
In previous post, we have discussed about Longest Bitonic Subsequence problem. However, the post only covered code related to finding maximum sum of increasing subsequence, but not to the construction of subsequence. In this post, we will discuss how to construct Longest Bitonic Subsequence itself. Let arr[0..n-1] be the input array. We define vector LIS such that LIS[i] is itself is a vector that stores Longest Increasing Subsequence of arr[0..i] that ends with arr[i]. Therefore for an index i, LIS[i] can be recursively written as –
LIS[0] = {arr[O]}
LIS[i] = {Max(LIS[j])} + arr[i] where j < i and arr[j] < arr[i]
= arr[i], if there is no such j
We also define a vector LDS such that LDS[i] is itself is a vector that stores Longest Decreasing Subsequence of arr[i..n] that starts with arr[i]. Therefore for an index i, LDS[i] can be recursively written as –
LDS[n] = {arr[n]}
LDS[i] = arr[i] + {Max(LDS[j])} where j > i and arr[j] < arr[i]
= arr[i], if there is no such j
For example, for array [1 11 2 10 4 5 2 1],
LIS[0]: 1 LIS[1]: 1 11 LIS[2]: 1 2 LIS[3]: 1 2 10 LIS[4]: 1 2 4 LIS[5]: 1 2 4 5 LIS[6]: 1 2 LIS[7]: 1
LDS[0]: 1 LDS[1]: 11 10 5 2 1 LDS[2]: 2 1 LDS[3]: 10 5 2 1 LDS[4]: 4 2 1 LDS[5]: 5 2 1 LDS[6]: 2 1 LDS[7]: 1
Therefore, Longest Bitonic Subsequence can be
LIS[1] + LDS[1] = [1 11 10 5 2 1] OR LIS[3] + LDS[3] = [1 2 10 5 2 1] OR LIS[5] + LDS[5] = [1 2 4 5 2 1]
Below is the implementation of above idea –
C++
/* Dynamic Programming solution to print Longest Bitonic Subsequence */#include <bits/stdc++.h>using namespace std;// Utility function to print Longest Bitonic// Subsequencevoid print(vector<int>& arr, int size){ for(int i = 0; i < size; i++) cout << arr[i] << " ";}// Function to construct and print Longest// Bitonic Subsequencevoid 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 programint main(){ int arr[] = { 1, 11, 2, 10, 4, 5, 2, 1 }; int n = sizeof(arr) / sizeof(arr[0]); printLBS(arr, n); return 0;} |
Java
/* Dynamic Programming solution to print Longest Bitonic Subsequence */import java.util.*;class GFG { // Utility function to print Longest Bitonic // Subsequence static void print(Vector<Integer> arr, int size) { for (int i = 0; i < size; i++) System.out.print(arr.elementAt(i) + " "); } // Function to construct and print Longest // Bitonic Subsequence static void printLBS(int[] arr, int n) { // LIS[i] stores the length of the longest // increasing subsequence ending with arr[i] @SuppressWarnings("unchecked") Vector<Integer>[] LIS = new Vector[n]; for (int i = 0; i < n; i++) LIS[i] = new Vector<>(); // initialize LIS[0] to arr[0] LIS[0].add(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[i] > arr[j]) && LIS[j].size() > LIS[i].size()) { for (int k : LIS[j]) if (!LIS[i].contains(k)) LIS[i].add(k); } } LIS[i].add(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] @SuppressWarnings("unchecked") Vector<Integer>[] LDS = new Vector[n]; for (int i = 0; i < n; i++) LDS[i] = new Vector<>(); // initialize LDS[n-1] to arr[n-1] LDS[n - 1].add(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()) for (int k : LDS[j]) if (!LDS[i].contains(k)) LDS[i].add(k); } LDS[i].add(arr[i]); } // reverse as vector as we're inserting at end for (int i = 0; i < n; i++) Collections.reverse(LDS[i]); /* * 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 Code public static void main(String[] args) { int[] arr = { 1, 11, 2, 10, 4, 5, 2, 1 }; int n = arr.length; printLBS(arr, n); }}// This code is contributed by// sanjeev2552 |
Python3
# Dynamic Programming solution to print Longest# Bitonic Subsequencedef _print(arr: list, size: int): for i in range(size): print(arr[i], end=" ")# Function to construct and print Longest# Bitonic Subsequencedef printLBS(arr: list, n: int): # LIS[i] stores the length of the longest # increasing subsequence ending with arr[i] LIS = [0] * n for i in range(n): LIS[i] = [] # initialize LIS[0] to arr[0] LIS[0].append(arr[0]) # Compute LIS values from left to right for i in range(1, n): # for every j less than i for j in range(i): if ((arr[j] < arr[i]) and (len(LIS[j]) > len(LIS[i]))): LIS[i] = LIS[j].copy() LIS[i].append(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] LDS = [0] * n for i in range(n): LDS[i] = [] # initialize LDS[n-1] to arr[n-1] LDS[n - 1].append(arr[n - 1]) # Compute LDS values from right to left for i in range(n - 2, -1, -1): # for every j greater than i for j in range(n - 1, i, -1): if ((arr[j] < arr[i]) and (len(LDS[j]) > len(LDS[i]))): LDS[i] = LDS[j].copy() LDS[i].append(arr[i]) # reverse as vector as we're inserting at end for i in range(n): LDS[i] = list(reversed(LDS[i])) # LDS[i] now stores Maximum Decreasing Subsequence # of arr[i..n] that starts with arr[i] max = 0 maxIndex = -1 for i in range(n): # Find maximum value of size of LIS[i] + size # of LDS[i] - 1 if (len(LIS[i]) + len(LDS[i]) - 1 > max): max = len(LIS[i]) + len(LDS[i]) - 1 maxIndex = i # print all but last element of LIS[maxIndex] vector _print(LIS[maxIndex], len(LIS[maxIndex]) - 1) # print all elements of LDS[maxIndex] vector _print(LDS[maxIndex], len(LDS[maxIndex]))# Driver Codeif __name__ == "__main__": arr = [1, 11, 2, 10, 4, 5, 2, 1] n = len(arr) printLBS(arr, n)# This code is contributed by# sanjeev2552 |
C#
/* Dynamic Programming solution to print longest Bitonic Subsequence */using System;using System.Linq;using System.Collections.Generic;class GFG { // Utility function to print longest Bitonic // Subsequence static void print(List<int> arr, int size) { for (int i = 0; i < size; i++) Console.Write(arr[i] + " "); } // Function to construct and print longest // Bitonic Subsequence static void printLBS(int[] arr, int n) { // LIS[i] stores the length of the longest // increasing subsequence ending with arr[i] List<int>[] LIS = new List<int>[n]; for (int i = 0; i < n; i++) LIS[i] = new List<int>(); // initialize LIS[0] to arr[0] LIS[0].Add(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[i] > arr[j]) && LIS[j].Count > LIS[i].Count) { foreach (int k in LIS[j]) if (!LIS[i].Contains(k)) LIS[i].Add(k); } } LIS[i].Add(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] List<int>[] LDS = new List<int>[n]; for (int i = 0; i < n; i++) LDS[i] = new List<int>(); // initialize LDS[n-1] to arr[n-1] LDS[n - 1].Add(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].Count > LDS[i].Count) foreach (int k in LDS[j]) if (!LDS[i].Contains(k)) LDS[i].Add(k); } LDS[i].Add(arr[i]); } // reverse as vector as we're inserting at end for (int i = 0; i < n; i++) LDS[i].Reverse(); /* * 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].Count + LDS[i].Count - 1 > max) { max = LIS[i].Count + LDS[i].Count - 1; maxIndex = i; } } // print all but last element of LIS[maxIndex] vector print(LIS[maxIndex], LIS[maxIndex].Count - 1); // print all elements of LDS[maxIndex] vector print(LDS[maxIndex], LDS[maxIndex].Count); } // Driver Code public static void Main(String[] args) { int[] arr = { 1, 11, 2, 10, 4, 5, 2, 1 }; int n = arr.Length; printLBS(arr, n); }}// This code is contributed by PrinciRaj1992 |
Javascript
// Function to print the longest bitonic subsequencefunction _print(arr, size) { for (let i = 0; i<size; i++) { process.stdout.write(arr[i]+' '); }}// Function to construct and print the longest bitonic subsequencefunction printLBS(arr, n) { // LIS[i] stores the length of the longest increasing subsequence ending with arr[i] let LIS = new Array(n); for (let i = 0; i < n; i++) { LIS[i] = []; } // initialize LIS[0] to arr[0] LIS[0].push(arr[0]); // Compute LIS values from left to right for (let i = 1; i < n; i++) { // for every j less than i for (let j = 0; j < i; j++) { if (arr[j] < arr[i] && LIS[j].length > LIS[i].length) { LIS[i] = LIS[j].slice(); } } LIS[i].push(arr[i]); } // LIS[i] now stores the 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] let LDS = new Array(n); for (let i = 0; i < n; i++) { LDS[i] = []; } // initialize LDS[n-1] to arr[n-1] LDS[n - 1].push(arr[n - 1]); // Compute LDS values from right to left for (let i = n - 2; i >= 0; i--) { // for every j greater than i for (let j = n - 1; j > i; j--) { if (arr[j] < arr[i] && LDS[j].length > LDS[i].length) { LDS[i] = LDS[j].slice(); } } LDS[i].push(arr[i]); } // reverse the LDS vector as we're inserting at the end for (let i = 0; i < n; i++) { LDS[i].reverse(); } // LDS[i] now stores the Maximum Decreasing Subsequence of arr[i..n] that starts with arr[i] let max = 0; let maxIndex = -1; for (let i = 0; i < n; i++) { // Find maximum value of size of LIS[i] + size of LDS[i] - 1 if (LIS[i].length + LDS[i].length - 1 > max) { max = LIS[i].length + LDS[i].length - 1; maxIndex = i; } } // print all but // print all but last element of LIS[maxIndex] array _print(LIS[maxIndex].slice(0, -1), LIS[maxIndex].length - 1); // print all elements of LDS[maxIndex] array _print(LDS[maxIndex], LDS[maxIndex].length);}// Driver programconst arr = [1, 11, 2, 10, 4, 5, 2, 1];const n = arr.length;printLBS(arr, n); |
Output:
1 11 10 5 2 1
Time complexity of above Dynamic Programming solution is O(n2). Auxiliary space used by the program is O(n2). This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!