/* Dynamic Programming solution to print Longest  Bitonic Subsequence */ #include    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; } 

/* 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 

# Dynamic Programming solution to print Longest # Bitonic Subsequence def _print(arr: list size: int): for i in range(size): print(arr[i] end=' ') # Function to construct and print Longest # Bitonic Subsequence def 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 Code if __name__ == '__main__': arr = [1 11 2 10 4 5 2 1] n = len(arr) printLBS(arr n) # This code is contributed by # sanjeev2552 

/* 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 

// Function to print the longest bitonic subsequence function _print(arr size) {  for (let i = 0; i<size; i++) {  process.stdout.write(arr[i]+' ');  } } // Function to construct and print the longest bitonic subsequence function 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 program const arr = [1 11 2 10 4 5 2 1]; const n = arr.length; printLBS(arr n);