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 1void 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 Codeint 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 approachimport 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 1def 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 Codeif __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 approachusing 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 1function 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> |
Output:
3
Time Complexity: O(N * logN)
Auxiliary Space: O(1)
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!
