Dada una array arr[] de N enteros, la tarea es encontrar la longitud de la subsecuencia más larga de modo que los elementos adyacentes de la subsecuencia tengan al menos un dígito en común.
Ejemplos:
Entrada: arr[] = {1, 12, 44, 29, 33, 96, 89}
Salida: 5
La subsecuencia más larga es {1 12 29 96 89}
Entrada: arr[] = {12, 23, 45, 43, 36, 97}
Salida: 4
La subsecuencia más larga es {12 23 43 36}
Enfoque: la idea es almacenar la longitud de la subsecuencia más larga para cada dígito presente en un elemento de la array.
- dp[i][d] representa la longitud de la subsecuencia más larga hasta el i-ésimo elemento si el dígito d es el dígito común.
- Declare una array cnt y establezca cnt[d] = 1 para cada dígito presente en el elemento actual.
- Considere cada dígito d como un dígito común y encuentre la subsecuencia de longitud máxima que termina en arr[i] como dp[i][d] = max(dp[j][d]+1) (0<=j<i).
- También busque un máximo local max(dp[i][d]) para el elemento actual.
- Después de encontrar el máximo local, actualice dp[i][d] para todos los dígitos presentes en el elemento actual hasta un máximo local.
- Esto es necesario ya que el máximo local representa la subsecuencia de longitud máxima para un elemento que tiene el dígito d.
Por ejemplo, considere arr[] = {24, 49, 96}.
El máximo local para 49 es 2 obtenido del dígito 4.
Este máximo local se usará para encontrar el máximo local para 96 con el dígito común 9.
Para eso se requiere que para todos los dígitos en 49, dp[i][d] debe ser ajustado al máximo local.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find maximum length subsequence
// such that adjacent elements have at least
// one common digit
#include <bits/stdc++.h>
using namespace std;
// Returns length of maximum length subsequence
int findSubsequence(int arr[], int n)
{
// To store the length of the
// maximum length subsequence
int len = 1;
// To store current element arr[i]
int tmp;
int i, j, d;
// To store the length of the sub-sequence
// ending at index i and having common digit d
int dp[n][10];
memset(dp, 0, sizeof(dp));
// To store digits present in current element
int cnt[10];
// To store length of maximum length subsequence
// ending at index i
int locMax;
// For first element maximum length is 1 for
// each digit
tmp = arr[0];
while (tmp > 0) {
dp[0][tmp % 10] = 1;
tmp /= 10;
}
// Find digits of each element, then find length
// of subsequence for each digit and then find
// local maximum
for (i = 1; i < n; i++) {
tmp = arr[i];
locMax = 1;
memset(cnt, 0, sizeof(cnt));
// Find digits in current element
while (tmp > 0) {
cnt[tmp % 10] = 1;
tmp /= 10;
}
// For each digit present find length of
// subsequence and find local maximum
for (d = 0; d <= 9; d++) {
if (cnt[d]) {
dp[i][d] = 1;
for (j = 0; j < i; j++) {
dp[i][d] = max(dp[i][d], dp[j][d] + 1);
locMax = max(dp[i][d], locMax);
}
}
}
// Update value of dp[i][d] for each digit
// present in current element to local maximum
// found.
for (d = 0; d <= 9; d++) {
if (cnt[d]) {
dp[i][d] = locMax;
}
}
// Update maximum length with local maximum
len = max(len, locMax);
}
return len;
}
// Driver code
int main()
{
int arr[] = { 1, 12, 44, 29, 33, 96, 89 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSubsequence(arr, n);
return 0;
}
Java
// Java program to find maximum length subsequence
// such that adjacent elements have at least
// one common digit
class GFG
{
// Returns length of maximum length subsequence
static int findSubsequence(int arr[], int n)
{
// To store the length of the
// maximum length subsequence
int len = 1;
// To store current element arr[i]
int tmp;
int i, j, d;
// To store the length of the sub-sequence
// ending at index i and having common digit d
int[][] dp = new int[n][10];
// To store digits present in current element
int[] cnt = new int[10];
// To store length of maximum length subsequence
// ending at index i
int locMax;
// For first element maximum length is 1 for
// each digit
tmp = arr[0];
while (tmp > 0)
{
dp[0][tmp % 10] = 1;
tmp /= 10;
}
// Find digits of each element, then find length
// of subsequence for each digit and then find
// local maximum
for (i = 1; i < n; i++)
{
tmp = arr[i];
locMax = 1;
for (int x = 0; x < 10; x++)
cnt[x]=0;
// Find digits in current element
while (tmp > 0)
{
cnt[tmp % 10] = 1;
tmp /= 10;
}
// For each digit present find length of
// subsequence and find local maximum
for (d = 0; d <= 9; d++)
{
if (cnt[d] > 0)
{
dp[i][d] = 1;
for (j = 0; j < i; j++)
{
dp[i][d] = Math.max(dp[i][d], dp[j][d] + 1);
locMax = Math.max(dp[i][d], locMax);
}
}
}
// Update value of dp[i][d] for each digit
// present in current element to local maximum
// found.
for (d = 0; d <= 9; d++)
{
if (cnt[d] > 0)
{
dp[i][d] = locMax;
}
}
// Update maximum length with local maximum
len = Math.max(len, locMax);
}
return len;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 1, 12, 44, 29, 33, 96, 89 };
int n = arr.length;
System.out.println(findSubsequence(arr, n));
}
}
// This code is contributed by mits
Python3
# Python3 program to find maximum # Length subsequence such that # adjacent elements have at least # one common digit # Returns Length of maximum # Length subsequence def findSubsequence(arr, n): # To store the Length of the # maximum Length subsequence Len = 1 # To store current element arr[i] tmp = 0 i, j, d = 0, 0, 0 # To store the Length of the sub-sequence # ending at index i and having common digit d dp = [[0 for i in range(10)] for i in range(n)] # To store digits present in current element cnt = [0 for i in range(10)] # To store Length of maximum # Length subsequence ending at index i locMax = 0 # For first element maximum # Length is 1 for each digit tmp = arr[0] while (tmp > 0): dp[0][tmp % 10] = 1 tmp //= 10 # Find digits of each element, # then find Length of subsequence # for each digit and then find # local maximum for i in range(1, n): tmp = arr[i] locMax = 1 cnt = [0 for i in range(10)] # Find digits in current element while (tmp > 0): cnt[tmp % 10] = 1 tmp //= 10 # For each digit present find Length of # subsequence and find local maximum for d in range(10): if (cnt[d]): dp[i][d] = 1 for j in range(i): dp[i][d] = max(dp[i][d], dp[j][d] + 1) locMax = max(dp[i][d], locMax) # Update value of dp[i][d] for each digit # present in current element to local # maximum found. for d in range(10): if (cnt[d]): dp[i][d] = locMax # Update maximum Length # with local maximum Len = max(Len, locMax) return Len # Driver code arr = [1, 12, 44, 29, 33, 96, 89] n = len(arr) print(findSubsequence(arr, n)) # This code is contributed # by mohit kumar
C#
// C# program to find maximum length subsequence
// such that adjacent elements have at least
// one common digit
using System;
class GFG
{
// Returns length of maximum length subsequence
static int findSubsequence(int []arr, int n)
{
// To store the length of the
// maximum length subsequence
int len = 1;
// To store current element arr[i]
int tmp;
int i, j, d;
// To store the length of the sub-sequence
// ending at index i and having common digit d
int[,] dp = new int[n, 10];
// To store digits present in current element
int[] cnt = new int[10];
// To store length of maximum length subsequence
// ending at index i
int locMax;
// For first element maximum length is 1 for
// each digit
tmp = arr[0];
while (tmp > 0)
{
dp[0, tmp % 10] = 1;
tmp /= 10;
}
// Find digits of each element, then find length
// of subsequence for each digit and then find
// local maximum
for (i = 1; i < n; i++)
{
tmp = arr[i];
locMax = 1;
for (int x = 0; x < 10; x++)
cnt[x] = 0;
// Find digits in current element
while (tmp > 0)
{
cnt[tmp % 10] = 1;
tmp /= 10;
}
// For each digit present find length of
// subsequence and find local maximum
for (d = 0; d <= 9; d++)
{
if (cnt[d] > 0)
{
dp[i, d] = 1;
for (j = 0; j < i; j++)
{
dp[i, d] = Math.Max(dp[i, d], dp[j, d] + 1);
locMax = Math.Max(dp[i, d], locMax);
}
}
}
// Update value of dp[i,d] for each digit
// present in current element to local maximum
// found.
for (d = 0; d <= 9; d++)
{
if (cnt[d] > 0)
{
dp[i, d] = locMax;
}
}
// Update maximum length with local maximum
len = Math.Max(len, locMax);
}
return len;
}
// Driver code
public static void Main()
{
int []arr = { 1, 12, 44, 29, 33, 96, 89 };
int n = arr.Length;
Console.WriteLine(findSubsequence(arr, n));
}
}
// This code is contributed by mits
Javascript
<script>
// Javascript program to find maximum length subsequence
// such that adjacent elements have at least
// one common digit
// Returns length of maximum length subsequence
function findSubsequence(arr,n)
{
// To store the length of the
// maximum length subsequence
let len = 1;
// To store current element arr[i]
let tmp;
let i, j, d;
// To store the length of the sub-sequence
// ending at index i and having common digit d
let dp = new Array(n);
for(let i = 0; i < n; i++)
{
dp[i] = new Array(10);
for(let j = 0; j < 10; j++)
{
dp[i][j] = 0;
}
}
// To store digits present in current element
let cnt = new Array(10);
// To store length of maximum length subsequence
// ending at index i
let locMax;
// For first element maximum length is 1 for
// each digit
tmp = arr[0];
while (tmp > 0)
{
dp[0][tmp % 10] = 1;
tmp = Math.floor(tmp/10);
}
// Find digits of each element, then find length
// of subsequence for each digit and then find
// local maximum
for (i = 1; i < n; i++)
{
tmp = arr[i];
locMax = 1;
for (let x = 0; x < 10; x++)
cnt[x]=0;
// Find digits in current element
while (tmp > 0)
{
cnt[tmp % 10] = 1;
tmp = Math.floor(tmp/10);
}
// For each digit present find length of
// subsequence and find local maximum
for (d = 0; d <= 9; d++)
{
if (cnt[d] > 0)
{
dp[i][d] = 1;
for (j = 0; j < i; j++)
{
dp[i][d] = Math.max(dp[i][d], dp[j][d] + 1);
locMax = Math.max(dp[i][d], locMax);
}
}
}
// Update value of dp[i][d] for each digit
// present in current element to local maximum
// found.
for (d = 0; d <= 9; d++)
{
if (cnt[d] > 0)
{
dp[i][d] = locMax;
}
}
// Update maximum length with local maximum
len = Math.max(len, locMax);
}
return len;
}
// Driver code
let arr=[ 1, 12, 44, 29, 33, 96, 89];
let n = arr.length;
document.write(findSubsequence(arr, n));
// This code is contributed by rag2127
</script>
Producción:
5
Complejidad de tiempo: O(n 2 )
Espacio auxiliar: O(n)
El espacio auxiliar requerido para la solución anterior se puede reducir aún más. Observe que para cada dígito d presente en arr[i], se requiere encontrar la subsecuencia de longitud máxima hasta ese dígito, independientemente del hecho de en qué elemento finalice la subsecuencia. Esto reduce el espacio auxiliar requerido a O(1). Para cada arr[i], encuentre el máximo local y actualice dig[d] para cada dígito d en arr[i] al máximo local.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find maximum length subsequence
// such that adjacent elements have at least
// one common digit
#include <bits/stdc++.h>
using namespace std;
// Returns length of maximum length subsequence
int findSubsequence(int arr[], int n)
{
// To store length of maximum length subsequence
int len = 1;
// To store current element arr[i]
int tmp;
int i, j, d;
// To store length of subsequence
// having common digit d
int dp[10];
memset(dp, 0, sizeof(dp));
// To store digits present in current element
int cnt[10];
// To store local maximum for current element
int locMax;
// For first element maximum length is 1 for
// each digit
tmp = arr[0];
while (tmp > 0) {
dp[tmp % 10] = 1;
tmp /= 10;
}
// Find digits of each element, then find length
// of subsequence for each digit and then find
// local maximum
for (i = 1; i < n; i++) {
tmp = arr[i];
locMax = 1;
memset(cnt, 0, sizeof(cnt));
// Find digits in current element
while (tmp > 0) {
cnt[tmp % 10] = 1;
tmp /= 10;
}
// For each digit present find length of
// subsequence and find local maximum
for (d = 0; d <= 9; d++) {
if (cnt[d]) {
dp[d]++;
locMax = max(locMax, dp[d]);
}
}
// Update value of dp[d] for each digit
// present in current element to local maximum
// found
for (d = 0; d <= 9; d++) {
if (cnt[d]) {
dp[d] = locMax;
}
}
// Update maximum length with local maximum
len = max(len, locMax);
}
return len;
}
// Driver code
int main()
{
int arr[] = { 1, 12, 44, 29, 33, 96, 89 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSubsequence(arr, n);
return 0;
}
Java
// Java program to find maximum length subsequence
// such that adjacent elements have at least
// one common digit
import java.util.*;
class GFG
{
// Returns length of maximum length subsequence
static int findSubsequence(int arr[], int n)
{
// To store length of maximum length subsequence
int len = 1;
// To store current element arr[i]
int tmp;
int i, j, d;
// To store length of subsequence
// having common digit d
int dp[] = new int[10];
// To store digits present in current element
int cnt[] = new int[10];
// To store local maximum for current element
int locMax;
// For first element maximum length is 1 for
// each digit
tmp = arr[0];
while (tmp > 0)
{
dp[tmp % 10] = 1;
tmp /= 10;
}
// Find digits of each element, then find length
// of subsequence for each digit and then find
// local maximum
for (i = 1; i < n; i++)
{
tmp = arr[i];
locMax = 1;
Arrays.fill(cnt, 0);
// Find digits in current element
while (tmp > 0)
{
cnt[tmp % 10] = 1;
tmp /= 10;
}
// For each digit present find length of
// subsequence and find local maximum
for (d = 0; d <= 9; d++)
{
if (cnt[d] == 1)
{
dp[d]++;
locMax = Math.max(locMax, dp[d]);
}
}
// Update value of dp[d] for each digit
// present in current element to local maximum
// found
for (d = 0; d <= 9; d++)
{
if (cnt[d] == 1)
{
dp[d] = locMax;
}
}
// Update maximum length with local maximum
len = Math.max(len, locMax);
}
return len;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 12, 44, 29, 33, 96, 89 };
int n = arr.length;
System.out.print(findSubsequence(arr, n));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 program to find maximum length # subsequence such that adjacent elements # have at least one common digit # Returns length of maximum # length subsequence def findSubsequence(arr, n) : # To store length of maximum # length subsequence length = 1; # To store length of subsequence # having common digit d dp = [0] * 10; # For first element maximum length # is 1 for each digit tmp = arr[0]; while (tmp > 0) : dp[tmp % 10] = 1; tmp //= 10; # Find digits of each element, then # find length of subsequence for each # digit and then find local maximum for i in range(1, n) : tmp = arr[i]; locMax = 1; cnt = [0] * 10 # Find digits in current element while (tmp > 0) : cnt[tmp % 10] = 1; tmp //= 10; # For each digit present find length of # subsequence and find local maximum for d in range(10) : if (cnt[d]) : dp[d] += 1; locMax = max(locMax, dp[d]); # Update value of dp[d] for each digit # present in current element to local # maximum found for d in range(10) : if (cnt[d]) : dp[d] = locMax; # Update maximum length with local # maximum length = max(length, locMax); return length; # Driver code if __name__ == "__main__" : arr = [ 1, 12, 44, 29, 33, 96, 89 ]; n = len(arr) print(findSubsequence(arr, n)); # This code is contributed by Ryuga
C#
// C# program to find maximum length subsequence
// such that adjacent elements have at least
// one common digit
using System;
class GFG
{
// Returns length of maximum length subsequence
static int findSubsequence(int []arr, int n)
{
// To store length of maximum length subsequence
int len = 1;
// To store current element arr[i]
int tmp;
int i, j, d;
// To store length of subsequence
// having common digit d
int []dp = new int[10];
// To store digits present in current element
int []cnt = new int[10];
// To store local maximum for current element
int locMax;
// For first element maximum length is 1 for
// each digit
tmp = arr[0];
while (tmp > 0)
{
dp[tmp % 10] = 1;
tmp /= 10;
}
// Find digits of each element, then find length
// of subsequence for each digit and then find
// local maximum
for (i = 1; i < n; i++)
{
tmp = arr[i];
locMax = 1;
for(int k = 0; k < 10; k++)
{
cnt[k] = 0;
}
// Find digits in current element
while (tmp > 0)
{
cnt[tmp % 10] = 1;
tmp /= 10;
}
// For each digit present find length of
// subsequence and find local maximum
for (d = 0; d <= 9; d++)
{
if (cnt[d] == 1)
{
dp[d]++;
locMax = Math.Max(locMax, dp[d]);
}
}
// Update value of dp[d] for each digit
// present in current element to local maximum
// found
for (d = 0; d <= 9; d++)
{
if (cnt[d] == 1)
{
dp[d] = locMax;
}
}
// Update maximum length with local maximum
len = Math.Max(len, locMax);
}
return len;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 12, 44, 29, 33, 96, 89 };
int n = arr.Length;
Console.WriteLine(findSubsequence(arr, n));
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP program to find maximum length subsequence
// such that adjacent elements have at least
// one common digit
// Returns length of maximum length subsequence
function findSubsequence($arr, $n)
{
// To store length of maximum length
// subsequence
$len = 1;
// To store length of subsequence
// having common digit d
$dp = array_fill(0, 10, NULL);
// For first element maximum length is 1
// for each digit
$tmp = $arr[0];
while ($tmp > 0)
{
$dp[$tmp % 10] = 1;
$tmp = intval($tmp / 10);
}
// Find digits of each element, then
// find length of subsequence for each
// digit and then find local maximum
for ($i = 1; $i < $n; $i++)
{
$tmp = $arr[$i];
$locMax = 1;
$cnt = array_fill(0, 10, NULL);
// Find digits in current element
while ($tmp > 0)
{
$cnt[$tmp % 10] = 1;
$tmp = intval($tmp / 10);
}
// For each digit present find length of
// subsequence and find local maximum
for ($d = 0; $d <= 9; $d++)
{
if ($cnt[$d])
{
$dp[$d]++;
$locMax = max($locMax, $dp[$d]);
}
}
// Update value of dp[d] for each digit
// present in current element to local
// maximum found
for ($d = 0; $d <= 9; $d++)
{
if ($cnt[$d])
{
$dp[$d] = $locMax;
}
}
// Update maximum length with
// local maximum
$len = max($len, $locMax);
}
return $len;
}
// Driver code
$arr = array( 1, 12, 44, 29, 33, 96, 89 );
$n = sizeof($arr);
echo findSubsequence($arr, $n);
// This code is contributed by ita_c
?>
Javascript
<script>
// JavaScript program to find maximum length subsequence
// such that adjacent elements have at least
// one common digit
// Returns length of maximum length subsequence
function findSubsequence(arr , n) {
// To store length of maximum length subsequence
var len = 1;
// To store current element arr[i]
var tmp;
var i, j, d;
// To store length of subsequence
// having common digit d
var dp = Array(10).fill(0);
// To store digits present in current element
var cnt = Array(10).fill(0);
// To store local maximum for current element
var locMax;
// For first element maximum length is 1 for
// each digit
tmp = arr[0];
while (tmp > 0) {
dp[tmp % 10] = 1;
tmp = parseInt(tmp/10);
}
// Find digits of each element, then find length
// of subsequence for each digit and then find
// local maximum
for (var i = 1; i < n; i++) {
tmp = arr[i];
locMax = 1;
cnt.fill( 0);
// Find digits in current element
while (tmp > 0) {
cnt[tmp % 10] = 1;
tmp = parseInt(tmp/10);
}
// For each digit present find length of
// subsequence and find local maximum
for (d = 0; d <= 9; d++) {
if (cnt[d] == 1) {
dp[d]++;
locMax = Math.max(locMax, dp[d]);
}
}
// Update value of dp[d] for each digit
// present in current element to local maximum
// found
for (d = 0; d <= 9; d++) {
if (cnt[d] == 1) {
dp[d] = locMax;
}
}
// Update maximum length with local maximum
len = Math.max(len, locMax);
}
return len;
}
// Driver code
var arr = [ 1, 12, 44, 29, 33, 96, 89 ];
var n = arr.length;
document.write(findSubsequence(arr, n));
// This code contributed by gauravrajput1
</script>
Producción:
5
Complejidad temporal: O(n)
Espacio auxiliar: O(1)