Given an arr[] of length N, the task is to find the length of longest Reverse Bitonic Subsequence. A subsequence is called Reverse Bitonic if it is first decreasing, then increasing.
Examples:
Input: arr[] = {10, 11, 2, 1, 1, 5, 2, 4}
Output: 5
Explanation: The longest subsequence which first decreases than increases is {10, 2, 1, 1, 2, 4}
Input: arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Output: 7
Explanation: The longest subsequence which first decreases than increases is {12, 10, 6, 1, 9, 11, 15}
Approach:
This problem is a variation of standard Longest Increasing Subsequence (LIS) problem. Construct two arrays lis[] and lds[] to store the longest increasing and decreasing subsequences respectively upto every ith index of the array using Dynamic Programming. Finally, return the max value of lds[i] + lis[i] – 1 where i ranges from 0 to N-1.
Below is the implementation of the above approach:
C++
// C++ program to find the// longest Reverse bitonic// Subsequence#include <bits/stdc++.h>using namespace std;// Function to return the length// of the Longest Reverse Bitonic// Subsequence in the arrayint ReverseBitonic(int arr[], int N){ int i, j; // Allocate memory for LIS[] and // initialize LIS values as 1 for // all indexes int lds[N]; for (i = 0; i < N; i++) { lds[i] = 1; } // Compute LIS values from left // to right for every index for (i = 1; i < N; i++) { for (j = 0; j < i; j++) { if (arr[i] < arr[j] && lds[i] < lds[j] + 1) { lds[i] = lds[j] + 1; } } } // Initialize LDS for // all indexes as 1 int lis[N]; for (i = 0; i < N; i++) { lis[i] = 1; } // Compute LDS values for every // index from right to left for (i = N - 2; i >= 0; i--) { for (j = N - 1; j > i; j--) { if (arr[i] < arr[j] && lis[i] < lis[j] + 1) { lis[i] = lis[j] + 1; } } } // Find the maximum value of // lis[i] + lds[i] - 1 // in the array int max = lis[0] + lds[0] - 1; for (i = 1; i < N; i++) { if (lis[i] + lds[i] - 1 > max) { max = lis[i] + lds[i] - 1; } } // Return the maximum return max;}// Driver Programint main(){ int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int N = sizeof(arr) / sizeof(arr[0]); printf("Length of LBS is %d\n", ReverseBitonic(arr, N)); return 0;} |
Java
// Java program to find the// longest Reverse bitonic// Subsequenceimport java.io.*; class GFG{ // Function to return the length// of the Longest Reverse Bitonic// Subsequence in the arraystatic int ReverseBitonic(int arr[], int N){ int i, j; // Allocate memory for LIS[] and // initialize LIS values as 1 for // all indexes int[] lds = new int[N]; for(i = 0; i < N; i++) { lds[i] = 1; } // Compute LIS values from left // to right for every index for(i = 1; i < N; i++) { for(j = 0; j < i; j++) { if (arr[i] < arr[j] && lds[i] < lds[j] + 1) { lds[i] = lds[j] + 1; } } } // Initialize LDS for // all indexes as 1 int[] lis = new int[N]; for(i = 0; i < N; i++) { lis[i] = 1; } // Compute LDS values for every // index from right to left for(i = N - 2; i >= 0; i--) { for(j = N - 1; j > i; j--) { if (arr[i] < arr[j] && lis[i] < lis[j] + 1) { lis[i] = lis[j] + 1; } } } // Find the maximum value of // lis[i] + lds[i] - 1 // in the array int max = lis[0] + lds[0] - 1; for(i = 1; i < N; i++) { if (lis[i] + lds[i] - 1 > max) { max = lis[i] + lds[i] - 1; } } // Return the maximum return max;}// Driver code public static void main (String[] args) { int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int N = arr.length; System.out.println("Length of LBS is " + ReverseBitonic(arr, N));} } // This code is contributed by jana_sayantan |
Python3
# Python3 program to find the # longest Reverse bitonic # Subsequence # Function to return the length # of the Longest Reverse Bitonic # Subsequence in the array def ReverseBitonic(arr): N = len(arr) # Allocate memory for LIS[] and # initialize LIS values as 1 # for all indexes lds = [1 for i in range(N + 1)] # Compute LIS values from left to right for i in range(1, N): for j in range(0 , i): if ((arr[i] < arr[j]) and (lds[i] < lds[j] + 1)): lds[i] = lds[j] + 1 # Allocate memory for LDS and # initialize LDS values for # all indexes lis = [1 for i in range(N + 1)] # Compute LDS values from right to left # Loop from n-2 downto 0 for i in reversed(range(N - 1)): # Loop from n-1 downto i-1 for j in reversed(range(i - 1, N)): if (arr[i] < arr[j] and lis[i] < lis[j] + 1): lis[i] = lis[j] + 1 # Return the maximum value of # (lis[i] + lds[i] - 1) maximum = lis[0] + lds[0] - 1 for i in range(1, N): maximum = max((lis[i] + lds[i] - 1), maximum) return maximum # Driver codearr = [ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 ] print("Length of LBS is", ReverseBitonic(arr))# This code is contributed by grand_master |
C#
// C# program to find the// longest Reverse bitonic// Subsequenceusing System; class GFG{ // Function to return the length// of the Longest Reverse Bitonic// Subsequence in the arraystatic int ReverseBitonic(int[] arr, int N){ int i, j; // Allocate memory for LIS[] and // initialize LIS values as 1 for // all indexes int[] lds = new int[N]; for(i = 0; i < N; i++) { lds[i] = 1; } // Compute LIS values from left // to right for every index for(i = 1; i < N; i++) { for(j = 0; j < i; j++) { if (arr[i] < arr[j] && lds[i] < lds[j] + 1) { lds[i] = lds[j] + 1; } } } // Initialize LDS for // all indexes as 1 int[] lis = new int[N]; for(i = 0; i < N; i++) { lis[i] = 1; } // Compute LDS values for every // index from right to left for(i = N - 2; i >= 0; i--) { for(j = N - 1; j > i; j--) { if (arr[i] < arr[j] && lis[i] < lis[j] + 1) { lis[i] = lis[j] + 1; } } } // Find the maximum value of // lis[i] + lds[i] - 1 // in the array int max = lis[0] + lds[0] - 1; for(i = 1; i < N; i++) { if (lis[i] + lds[i] - 1 > max) { max = lis[i] + lds[i] - 1; } } // Return the maximum return max;}// Driver code public static void Main () { int[] arr = new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int N = arr.Length; Console.WriteLine("Length of LBS is " + ReverseBitonic(arr, N));} }// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript program to find the// longest Reverse bitonic// Subsequence// Function to return the length// of the Longest Reverse Bitonic// Subsequence in the arrayfunction ReverseBitonic(arr, N){ let i, j; // Allocate memory for LIS[] and // initialize LIS values as 1 for // all indexes let lds = []; for(i = 0; i < N; i++) { lds[i] = 1; } // Compute LIS values from left // to right for every index for(i = 1; i < N; i++) { for(j = 0; j < i; j++) { if (arr[i] < arr[j] && lds[i] < lds[j] + 1) { lds[i] = lds[j] + 1; } } } // Initialize LDS for // all indexes as 1 let lis = []; for(i = 0; i < N; i++) { lis[i] = 1; } // Compute LDS values for every // index from right to left for(i = N - 2; i >= 0; i--) { for(j = N - 1; j > i; j--) { if (arr[i] < arr[j] && lis[i] < lis[j] + 1) { lis[i] = lis[j] + 1; } } } // Find the maximum value of // lis[i] + lds[i] - 1 // in the array let max = lis[0] + lds[0] - 1; for(i = 1; i < N; i++) { if (lis[i] + lds[i] - 1 > max) { max = lis[i] + lds[i] - 1; } } // Return the maximum return max;}// Driver Code let arr = [ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 ]; let N = arr.length; document.write("Length of LBS is " + ReverseBitonic(arr, N)); // This code is contributed by avijitmondal1998.</script> |
Output:
Length of LBS is 7
Time Complexity: O(N2)
Auxiliary Space: O(N)
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!
