Longitud de la subsecuencia no decreciente más larga tal que la diferencia entre elementos adyacentes es como máximo uno

Dada una array arr[] que consta de N enteros, la tarea es encontrar la longitud de la subsecuencia no decreciente más larga tal que la diferencia entre elementos adyacentes sea como máximo 1 .

Ejemplos:

Entrada: arr[] = {8, 5, 4, 8, 4}
Salida: 3
Explicación:  {4, 4, 5}, {8, 8} son las dos subsecuencias no decrecientes de longitud 2 y 3 respectivamente. Por lo tanto, la longitud de la más larga de las dos subsecuencias es 3. 

Entrada: arr[] = {4, 13, 2, 3}
Salida: 3
Explicación:  {2, 3, 4}, {13} son las dos subsecuencias no decrecientes de longitud 3 y 1 respectivamente. Por lo tanto, la longitud de la más larga de las dos subsecuencias es 3. 

Enfoque : siga los pasos a continuación para resolver el problema:

• Ordene la array arr[] en orden creciente .
• Inicialice una variable, digamos maxLen = 1, para almacenar la longitud máxima posible de una subsecuencia. Inicialice otra variable, digamos len = 1 para almacenar la longitud actual de cada subsecuencia.
• Recorra la array arr[] con un puntero i y para cada elemento:
  • Compruebe si abs(arr[i] – arr[i – 1]) ≤ 1 . Si se encuentra que es cierto, entonces incremente len en 1 . Actualice maxLen = max(maxLen, len) .
  • De lo contrario, establezca len = 1 , es decir, comience una nueva subsecuencia.
• Imprime el valor de maxLen como respuesta final.

A continuación se muestra la implementación del enfoque anterior:

// 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 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);
    }
}

# 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# 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

<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

Complejidad de tiempo: O(N * logN)
Espacio auxiliar: O(1)