Dada una array de n enteros. El problema es encontrar la longitud máxima de la subsecuencia con diferencia entre elementos adyacentes como 0 o 1.
Ejemplos:
Input : arr[] = {2, 5, 6, 3, 7, 6, 5, 8}
Output : 5
The subsequence is {5, 6, 7, 6, 5}.
Input : arr[] = {-2, -1, 5, -1, 4, 0, 3}
Output : 4
The subsequence is {-2, -1, -1, 0}.
Fuente: Experiencia de entrevista de Expedia | conjunto 12
La solución a este problema se parece mucho al problema de la subsecuencia creciente más larga . La única diferencia es que aquí tenemos que verificar si la diferencia absoluta entre los elementos adyacentes de la subsecuencia es 0 o 1.
C++
// C++ implementation to find maximum length
// subsequence with difference between adjacent
// elements as either 0 or 1
#include <bits/stdc++.h>
using namespace std;
// function to find maximum length subsequence
// with difference between adjacent elements as
// either 0 or 1
int maxLenSub(int arr[], int n)
{
int mls[n], max = 0;
// Initialize mls[] values for all indexes
for (int i=0; i<n; i++)
mls[i] = 1;
// Compute optimized maximum length subsequence
// values in bottom up manner
for (int i=1; i<n; i++)
for (int j=0; j<i; j++)
if (abs(arr[i] - arr[j]) <= 1 &&
mls[i] < mls[j] + 1)
mls[i] = mls[j] + 1;
// Store maximum of all 'mls' values in 'max'
for (int i=0; i<n; i++)
if (max < mls[i])
max = mls[i];
// required maximum length subsequence
return max;
}
// Driver program to test above
int main()
{
int arr[] = {2, 5, 6, 3, 7, 6, 5, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum length subsequence = "
<< maxLenSub(arr, n);
return 0;
}
Java
// JAVA Code for Maximum length subsequence
// with difference between adjacent elements
// as either 0 or 1
import java.util.*;
class GFG {
// function to find maximum length subsequence
// with difference between adjacent elements as
// either 0 or 1
public static int maxLenSub(int arr[], int n)
{
int mls[] = new int[n], max = 0;
// Initialize mls[] values for all indexes
for (int i = 0; i < n; i++)
mls[i] = 1;
// Compute optimized maximum length
// subsequence values in bottom up manner
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (Math.abs(arr[i] - arr[j]) <= 1
&& mls[i] < mls[j] + 1)
mls[i] = mls[j] + 1;
// Store maximum of all 'mls' values in 'max'
for (int i = 0; i < n; i++)
if (max < mls[i])
max = mls[i];
// required maximum length subsequence
return max;
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = {2, 5, 6, 3, 7, 6, 5, 8};
int n = arr.length;
System.out.println("Maximum length subsequence = "+
maxLenSub(arr, n));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python implementation to find maximum length
# subsequence with difference between adjacent
# elements as either 0 or 1
# function to find maximum length subsequence
# with difference between adjacent elements as
# either 0 or 1
def maxLenSub( arr, n):
mls=[]
max = 0
#Initialize mls[] values for all indexes
for i in range(n):
mls.append(1)
#Compute optimized maximum length subsequence
# values in bottom up manner
for i in range(n):
for j in range(i):
if (abs(arr[i] - arr[j]) <= 1 and mls[i] < mls[j] + 1):
mls[i] = mls[j] + 1
# Store maximum of all 'mls' values in 'max'
for i in range(n):
if (max < mls[i]):
max = mls[i]
#required maximum length subsequence
return max
#Driver program to test above
arr = [2, 5, 6, 3, 7, 6, 5, 8]
n = len(arr)
print("Maximum length subsequence = ",maxLenSub(arr, n))
#This code is contributed by "Abhishek Sharma 44"
C#
// C# Code for Maximum length subsequence
// with difference between adjacent elements
// as either 0 or 1
using System;
class GFG {
// function to find maximum length subsequence
// with difference between adjacent elements as
// either 0 or 1
public static int maxLenSub(int[] arr, int n)
{
int[] mls = new int[n];
int max = 0;
// Initialize mls[] values for all indexes
for (int i = 0; i < n; i++)
mls[i] = 1;
// Compute optimized maximum length
// subsequence values in bottom up manner
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (Math.Abs(arr[i] - arr[j]) <= 1
&& mls[i] < mls[j] + 1)
mls[i] = mls[j] + 1;
// Store maximum of all 'mls' values in 'max'
for (int i = 0; i < n; i++)
if (max < mls[i])
max = mls[i];
// required maximum length subsequence
return max;
}
/* Driver program to test above function */
public static void Main()
{
int[] arr = { 2, 5, 6, 3, 7, 6, 5, 8 };
int n = arr.Length;
Console.Write("Maximum length subsequence = " +
maxLenSub(arr, n));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP implementation to find maximum length
// subsequence with difference between adjacent
// elements as either 0 or 1
// function to find maximum length subsequence
// with difference between adjacent elements as
// either 0 or 1
function maxLenSub($arr, $n)
{
$mls = array(); $max = 0;
// Initialize mls[] values
// for all indexes
for($i = 0; $i < $n; $i++)
$mls[$i] = 1;
// Compute optimized maximum
// length subsequence
// values in bottom up manner
for ($i = 1; $i < $n; $i++)
for ( $j = 0; $j < $i; $j++)
if (abs($arr[$i] - $arr[$j]) <= 1 and
$mls[$i] < $mls[$j] + 1)
$mls[$i] = $mls[$j] + 1;
// Store maximum of all
// 'mls' values in 'max'
for($i = 0; $i < $n; $i++)
if ($max < $mls[$i])
$max = $mls[$i];
// required maximum
// length subsequence
return $max;
}
// Driver Code
$arr = array(2, 5, 6, 3, 7, 6, 5, 8);
$n = count($arr);
echo "Maximum length subsequence = "
, maxLenSub($arr, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript Code for
// Maximum length subsequence
// with difference between
// adjacent elements
// as either 0 or 1
// function to find maximum
// length subsequence
// with difference between
// adjacent elements as
// either 0 or 1
function maxLenSub(arr, n)
{
let mls = new Array(n).fill(1), max = 0;
// Initialize mls[] values for all indexes
for (let i = 0; i < n; i++)
mls[i] = 1;
// Compute optimized maximum length
// subsequence values in bottom up manner
for (let i = 1; i < n; i++)
for (let j = 0; j < i; j++)
if (Math.abs(arr[i] - arr[j]) <= 1
&& mls[i] < mls[j] + 1)
mls[i] = mls[j] + 1;
// Store maximum of all 'mls' values in 'max'
for (let i = 0; i < n; i++)
if (max < mls[i])
max = mls[i];
// required maximum length subsequence
return max;
}
// driver program
let arr = [2, 5, 6, 3, 7, 6, 5, 8];
let n = arr.length;
document.write("Maximum length subsequence = "+
maxLenSub(arr, n));
</script>
Producción:
Maximum length subsequence = 5
Complejidad de tiempo: O(n 2 )
Espacio auxiliar: O(n)
Subsecuencia de longitud máxima con diferencia entre elementos adyacentes como 0 o 1 | Conjunto 2
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA