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