Subsecuencia no decreciente más larga que tiene una diferencia entre elementos adyacentes menor que D

Dada una array arr[] de N enteros y un entero D , la tarea es encontrar la longitud de la subsecuencia no decreciente más larga tal que la diferencia entre cada elemento adyacente sea menor que D.

Ejemplos:

Entrada: arr[] = {1, 3, 2, 4, 5}, D = 2
Salida: 3
Explicación:
Considere la subsecuencia como {3, 4, 5}, que tiene una longitud máxima = 3 que satisface los criterios dados.

Entrada: arr[] = {1, 5, 3, 2, 7}, D = 2
Salida: 2

Enfoque: el problema dado es una variación de la subsecuencia creciente más larga con criterios para la diferencia entre los elementos de array adyacentes como menos de D , esta idea se puede implementar utilizando la programación dinámica . Siga los pasos a continuación para resolver el problema dado:

  • Inicialice una array dp , donde dp[i] almacenará la longitud máxima de la subsecuencia no decreciente después de incluir el i ésimo elemento de modo que la diferencia entre cada par de elementos adyacentes sea menor que D.
  • Inicialice todos los valores de la array dp[] como 1 .
  • Itere un ciclo sobre el rango [0, N] y en cada iteración, atravieso la array dada arr[] sobre el rango [0, i – 1] usando la variable j y si el valor de arr[j] es al menos arr[i] y la diferencia entre ellos es menor que D , luego actualice el valor de dp[i] al máximo de dp[i] y (1 + dp[j]) .
  • Después de completar los pasos anteriores, imprima el valor máximo de la array dp[] como resultado.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the length of the
// longest non-decreasing subsequence
// having the difference as D for every
// adjacent elements
int longestSubsequence(vector<int> arr,
                       int d)
{
    // Store the size of array
    int n = arr.size();
 
    // Stores the maximum length of the
    // subsequence after including the
    // ith element
    vector<int> dp(n, 1);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
 
            // If it satisfies the
            // given condition
            if (arr[i] - d < arr[j]
                and arr[i] >= arr[j]) {
 
                // Update dp[i]
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
 
    // Maximum value in the dp
    // table is the answer
    return *max_element(
        dp.begin(), dp.end());
}
 
// Driver Code
int main()
{
    vector<int> arr = { 1, 3, 2, 4, 5 };
    int D = 2;
    cout << longestSubsequence(arr, D);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public class GFG {
     
    // Function to return the length of the
    // longest non-decreasing subsequence
    // having the difference as D for every
    // adjacent elements
    static int longestSubsequence(int  []arr,
                           int d)
    {
       
        // Store the size of array
        int n = arr.length;
     
        // Stores the maximum length of the
        // subsequence after including the
        // ith element
        int []dp = new int[n];
         
        for(int i = 0; i < n ; i++)
            dp[i] = 1;
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
     
                // If it satisfies the
                // given condition
                if (arr[i] - d < arr[j] && arr[i] >= arr[j]) {
     
                    // Update dp[i]
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
     
        // Maximum value in the dp
        // table is the answer
        Arrays.sort(dp);
        return dp[n - 1];
    }
     
    // Driver Code
    public static void main (String[] args) {
        int arr[] = { 1, 3, 2, 4, 5 };
        int D = 2;
        System.out.println(longestSubsequence(arr, D));
    }
}
 
// This code is contributed by AnkThon

Python3

# python program for the above approach
 
# Function to return the length of the
# longest non-decreasing subsequence
# having the difference as D for every
# adjacent elements
def longestSubsequence(arr, d):
 
    # Store the size of array
    n = len(arr)
 
    # Stores the maximum length of the
    # subsequence after including the
    # ith element
    dp = [1 for _ in range(n)]
 
    for i in range(0, n):
        for j in range(0, i):
 
            # If it satisfies the
            # given condition
            if (arr[i] - d < arr[j] and arr[i] >= arr[j]):
 
                # Update dp[i]
                dp[i] = max(dp[i], dp[j] + 1)
 
    # Maximum value in the dp
    # table is the answer
    return max(dp)
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 3, 2, 4, 5]
    D = 2
    print(longestSubsequence(arr, D))
 
    # This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
 
public class GFG {
     
    // Function to return the length of the
    // longest non-decreasing subsequence
    // having the difference as D for every
    // adjacent elements
    static int longestSubsequence(int  []arr,
                           int d)
    {
       
        // Store the size of array
        int n = arr.Length;
     
        // Stores the maximum length of the
        // subsequence after including the
        // ith element
        int []dp = new int[n];
         
        for(int i = 0; i < n ; i++)
            dp[i] = 1;
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
     
                // If it satisfies the
                // given condition
                if (arr[i] - d < arr[j] && arr[i] >= arr[j]) {
     
                    // Update dp[i]
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }
     
        // Maximum value in the dp
        // table is the answer
        Array.Sort(dp);
        return dp[n - 1];
    }
     
    // Driver Code
    public static void Main (string[] args) {
        int []arr = { 1, 3, 2, 4, 5 };
        int D = 2;
        Console.WriteLine(longestSubsequence(arr, D));
    }
}
 
// This code is contributed by AnkThon

Javascript

<script>
// Javascript program for the above approach
 
// Function to return the length of the
// longest non-decreasing subsequence
// having the difference as D for every
// adjacent elements
function longestSubsequence(arr, d)
{
 
  // Store the size of array
  let n = arr.length;
 
  // Stores the maximum length of the
  // subsequence after including the
  // ith element
  let dp = new Array(n).fill(1);
 
  for (let i = 0; i < n; i++)
  {
    for (let j = 0; j < i; j++)
    {
     
      // If it satisfies the
      // given condition
      if (arr[i] - d < arr[j] && arr[i] >= arr[j])
      {
       
        // Update dp[i]
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
 
  // Maximum value in the dp
  // table is the answer
  return dp.sort((a, b) => b - a)[0];
}
 
// Driver Code
let arr = [1, 3, 2, 4, 5];
let D = 2;
document.write(longestSubsequence(arr, D));
 
// This code is contributed by gfgking.
</script>
Producción: 

3

 

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *