Given an array arr[] consisting of N integers, the task is to find the length of the longest non-decreasing subsequence such that the difference between adjacent elements is at most 1.
Examples:
Input: arr[] = {8, 5, 4, 8, 4}
Output: 3
Explanation: {4, 4, 5}, {8, 8} are the two such non-decreasing subsequences of length 2 and 3 respectively. Therefore, the length of the longest of the two subsequences is 3.Input: arr[] = {4, 13, 2, 3}
Output: 3
Explanation: {2, 3, 4}, {13} are the two such non-decreasing subsequences of length 3 and 1 respectively. Therefore, the length of the longest of the two subsequences is 3.
Approach: Follow the steps below to solve the problem:
- Sort the array arr[] in increasing order.
- Initialize a variable, say maxLen = 1, to store the maximum possible length of a subsequence. Initialize another variable, say len = 1 to store the current length for each subsequence.
- Traverse the array arr[] with a pointer i and for each element:
- Check if abs(arr[i] – arr[i – 1]) ? 1. If found to be true, then increment len by 1. Update maxLen = max(maxLen, len).
- Otherwise, set len = 1 i.e. start a new subsequence.
- Print the value of maxLen as the final answer.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the longest non-decreasing // subsequence with difference between // adjacent elements exactly equal to 1 void longestSequence( int arr[], int N) { // Base case if (N == 0) { cout << 0; return ; } // Sort the array in ascending order sort(arr, arr+N); // Stores the maximum length int maxLen = 1; int len = 1; // Traverse the array for ( int i = 1; i < N; i++) { // If difference between current // pair of adjacent elements is 1 or 0 if (arr[i] == arr[i - 1] || arr[i] == arr[i - 1] + 1) { len++; // Extend the current sequence // Update len and max_len maxLen = max(maxLen, len); } else { // Otherwise, start a new subsequence len = 1; } } // Print the maximum length cout << maxLen; } // Driver Code int main() { // Given array int arr[] = { 8, 5, 4, 8, 4 }; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); // Function call to find the longest // subsequence longestSequence(arr, N); return 0; } // This code is contributed by code_hunt. |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to find the longest non-decreasing // subsequence with difference between // adjacent elements exactly equal to 1 static void longestSequence( int arr[], int N) { // Base case if (N == 0 ) { System.out.println( 0 ); return ; } // Sort the array in ascending order Arrays.sort(arr); // Stores the maximum length int maxLen = 1 ; int len = 1 ; // Traverse the array for ( int i = 1 ; i < N; i++) { // If difference between current // pair of adjacent elements is 1 or 0 if (arr[i] == arr[i - 1 ] || arr[i] == arr[i - 1 ] + 1 ) { len++; // Extend the current sequence // Update len and max_len maxLen = Math.max(maxLen, len); } else { // Otherwise, start a new subsequence len = 1 ; } } // Print the maximum length System.out.println(maxLen); } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 8 , 5 , 4 , 8 , 4 }; // Size of the array int N = arr.length; // Function call to find the longest // subsequence longestSequence(arr, N); } } |
Python3
# Python program for the above approach # Function to find the longest non-decreasing # subsequence with difference between # adjacent elements exactly equal to 1 def longestSequence(arr, N): # Base case if (N = = 0 ): print ( 0 ); return ; # Sort the array in ascending order arr.sort(); # Stores the maximum length maxLen = 1 ; len = 1 ; # Traverse the array for i in range ( 1 ,N): # If difference between current # pair of adjacent elements is 1 or 0 if (arr[i] = = arr[i - 1 ] or arr[i] = = arr[i - 1 ] + 1 ): len + = 1 ; # Extend the current sequence # Update len and max_len maxLen = max (maxLen, len ); else : # Otherwise, start a new subsequence len = 1 ; # Print the maximum length print (maxLen); # Driver Code if __name__ = = '__main__' : # Given array arr = [ 8 , 5 , 4 , 8 , 4 ]; # Size of the array N = len (arr); # Function call to find the longest # subsequence longestSequence(arr, N); # This code is contributed by 29AjayKumar |
C#
// C# program for the above approach using System; public class GFG { // Function to find the longest non-decreasing // subsequence with difference between // adjacent elements exactly equal to 1 static void longestSequence( int []arr, int N) { // Base case if (N == 0) { Console.WriteLine(0); return ; } // Sort the array in ascending order Array.Sort(arr); // Stores the maximum length int maxLen = 1; int len = 1; // Traverse the array for ( int i = 1; i < N; i++) { // If difference between current // pair of adjacent elements is 1 or 0 if (arr[i] == arr[i - 1] || arr[i] == arr[i - 1] + 1) { len++; // Extend the current sequence // Update len and max_len maxLen = Math.Max(maxLen, len); } else { // Otherwise, start a new subsequence len = 1; } } // Print the maximum length Console.WriteLine(maxLen); } // Driver Code public static void Main( string [] args) { // Given array int []arr = { 8, 5, 4, 8, 4 }; // Size of the array int N = arr.Length; // Function call to find the longest // subsequence longestSequence(arr, N); } } // This code is contributed by AnkThon |
Javascript
<script> // Javascript program to implement // the above approach // Function to find the longest non-decreasing // subsequence with difference between // adjacent elements exactly equal to 1 function longestSequence(arr, N) { // Base case if (N == 0) { document.write(0); return ; } // Sort the array in ascending order arr.sort(); // Stores the maximum length var maxLen = 1; var len = 1; var i; // Traverse the array for (i = 1; i < N; i++) { // If difference between current // pair of adjacent elements is 1 or 0 if (arr[i] == arr[i - 1] || arr[i] == arr[i - 1] + 1) { len++; // Extend the current sequence // Update len and max_len maxLen = Math.max(maxLen, len); } else { // Otherwise, start a new subsequence len = 1; } } // Print the maximum length document.write(maxLen); } // Driver Code // Given array var arr = [8, 5, 4, 8, 4]; // Size of the array var N = arr.length; // Function call to find the longest // subsequence longestSequence(arr, N); </script> |
3
Time Complexity: O(N * logN)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!