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