Dada una secuencia de enteros positivos de longitud N . La única operación permitida es insertar un solo entero de cualquier valor en cualquier posición de la secuencia. La tarea es encontrar la subsecuencia de longitud máxima que contiene valores consecutivos en orden creciente.
Ejemplos:
Entrada: arr[] = {2, 1, 4, 5}
Salida: 4
Insertar elemento con valor 3 en la 3ra posición (indexación basada en 1)
La nueva secuencia se convierte en {2, 1, 3, 4, 5}
Más larga la subsecuencia consecutiva sería {2, 3, 4, 5}Entrada: arr[] = {2, 1, 2, 3, 5, 7}
Salida: 5
Enfoque: La idea es utilizar Programación Dinámica .
Sea dp[val][0] la longitud de la subsecuencia requerida que termina en un elemento igual a val y el elemento aún no se inserta. Sea dp[val][1] la longitud de la subsecuencia requerida que termina en un elemento igual a val y ya se ha insertado algún elemento.
Ahora divida el problema en sus subproblemas de la siguiente manera:
Para calcular dp[val][0], como no se inserta ningún elemento, la longitud de la subsecuencia aumentará en 1 desde su valor anterior
dp[val][0] = 1 + dp [valor-1][0] .
Para calcular dp[val][1], considere estos dos casos:
- Cuando el elemento ya está insertado para (val-1), entonces habría un incremento de longitud 1 desde dp[ val-1 ][ 1 ]
- Cuando el elemento aún no se ha insertado, se puede insertar el elemento con valor (val-1). Por lo tanto, habría un incremento de longitud 2 desde dp[ val-2 ][ 0 ].
Tome el máximo de los dos casos anteriores.
dp[val][1] = max(1 + dp[val – 1][1], 2 + dp[val – 2][0]) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the length of longest
// consecuetive subsequence after inserting an element
int LongestConsSeq(int arr[], int N)
{
// Variable to find maximum value of the array
int maxval = 1;
// Calculating maximum value of the array
for (int i = 0; i < N; i += 1) {
maxval = max(maxval, arr[i]);
}
// Declaring the DP table
int dp[maxval + 1][2] = { 0 };
// Variable to store the maximum length
int ans = 1;
// Iterating for every value present in the array
for (int i = 0; i < N; i += 1) {
// Recurrence for dp[val][0]
dp[arr[i]][0] = (1 + dp[arr[i] - 1][0]);
// No value can be inserted before 1,
// hence the element value should be
// greater than 1 for this recurrence relation
if (arr[i] >= 2)
// Recurrence for dp[val][1]
dp[arr[i]][1] = max(1 + dp[arr[i] - 1][1],
2 + dp[arr[i] - 2][0]);
else
// Maximum length of consecutive sequence
// ending at 1 is equal to 1
dp[arr[i]][1] = 1;
// Update the ans variable with
// the new maximum length possible
ans = max(ans, dp[arr[i]][1]);
}
// Return the ans
return ans;
}
// Driver code
int main()
{
// Input array
int arr[] = { 2, 1, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << LongestConsSeq(arr, N);
return 0;
}
Java
// Java implementation of above approach
class GFG
{
// Function to return the length of longest
// consecuetive subsequence after inserting an element
static int LongestConsSeq(int [] arr, int N)
{
// Variable to find maximum value of the array
int maxval = 1;
// Calculating maximum value of the array
for (int i = 0; i < N; i += 1)
{
maxval = Math. max(maxval, arr[i]);
}
// Declaring the DP table
int [][] dp = new int[maxval + 1][2];
// Variable to store the maximum length
int ans = 1;
// Iterating for every value present in the array
for (int i = 0; i < N; i += 1)
{
// Recurrence for dp[val][0]
dp[arr[i]][0] = (1 + dp[arr[i] - 1][0]);
// No value can be inserted before 1,
// hence the element value should be
// greater than 1 for this recurrence relation
if (arr[i] >= 2)
// Recurrence for dp[val][1]
dp[arr[i]][1] = Math.max(1 + dp[arr[i] - 1][1],
2 + dp[arr[i] - 2][0]);
else
// Maximum length of consecutive sequence
// ending at 1 is equal to 1
dp[arr[i]][1] = 1;
// Update the ans variable with
// the new maximum length possible
ans = Math.max(ans, dp[arr[i]][1]);
}
// Return the ans
return ans;
}
// Driver code
public static void main (String[] args)
{
// Input array
int [] arr = { 2, 1, 4, 5 };
int N = arr.length;
System.out.println(LongestConsSeq(arr, N));
}
}
// This code is contributed by ihritik
Python3
# Python3 implementation of above approach # Function to return the length of longest # consecuetive subsequence after inserting an element def LongestConsSeq(arr, N): # Variable to find maximum value of the array maxval = 1 # Calculating maximum value of the array for i in range(N): maxval = max(maxval, arr[i]) # Declaring the DP table dp=[[ 0 for i in range(2)] for i in range(maxval + 1)] # Variable to store the maximum length ans = 1 # Iterating for every value present in the array for i in range(N): # Recurrence for dp[val][0] dp[arr[i]][0] = 1 + dp[arr[i] - 1][0] # No value can be inserted before 1, # hence the element value should be # greater than 1 for this recurrence relation if (arr[i] >= 2): # Recurrence for dp[val][1] dp[arr[i]][1] = max(1 + dp[arr[i] - 1][1], 2 + dp[arr[i] - 2][0]) else: # Maximum length of consecutive sequence # ending at 1 is equal to 1 dp[arr[i]][1] = 1 # Update the ans variable with # the new maximum length possible ans = max(ans, dp[arr[i]][1]) # Return the ans return ans # Driver code arr=[2, 1, 4, 5] N = len(arr) print(LongestConsSeq(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to return the length of longest
// consecuetive subsequence after inserting an element
static int LongestConsSeq(int [] arr, int N)
{
// Variable to find maximum value of the array
int maxval = 1;
// Calculating maximum value of the array
for (int i = 0; i < N; i += 1)
{
maxval =Math.Max(maxval, arr[i]);
}
// Declaring the DP table
int [ , ] dp = new int[maxval + 1, 2];
// Variable to store the maximum length
int ans = 1;
// Iterating for every value present in the array
for (int i = 0; i < N; i += 1)
{
// Recurrence for dp[val][0]
dp[arr[i], 0] = (1 + dp[arr[i] - 1, 0]);
// No value can be inserted before 1,
// hence the element value should be
// greater than 1 for this recurrence relation
if (arr[i] >= 2)
// Recurrence for dp[val][1]
dp[arr[i], 1] = Math.Max(1 + dp[arr[i] - 1, 1],
2 + dp[arr[i] - 2, 0]);
else
// Maximum length of consecutive sequence
// ending at 1 is equal to 1
dp[arr[i], 1] = 1;
// Update the ans variable with
// the new maximum length possible
ans = Math.Max(ans, dp[arr[i], 1]);
}
// Return the ans
return ans;
}
// Driver code
public static void Main ()
{
// Input array
int [] arr = new int [] { 2, 1, 4, 5 };
int N = arr.Length;
Console.WriteLine(LongestConsSeq(arr, N));
}
}
// This code is contributed by ihritik
Javascript
<script>
// Javascript implementation of above approach
// Function to return the length of
// longest consecuetive subsequence
// after inserting an element
function LongestConsSeq(arr, N)
{
// Variable to find maximum value of the array
let maxval = 1;
// Calculating maximum value of the array
for(let i = 0; i < N; i += 1)
{
maxval = Math. max(maxval, arr[i]);
}
// Declaring the DP table
let dp = new Array(maxval + 1);
for(let i = 0; i < dp.length; i++)
{
dp[i] = new Array(2);
for(let j = 0; j < 2; j++)
dp[i][j] = 0;
}
// Variable to store the maximum length
let ans = 1;
// Iterating for every value present in the array
for(let i = 0; i < N; i += 1)
{
// Recurrence for dp[val][0]
dp[arr[i]][0] = (1 + dp[arr[i] - 1][0]);
// No value can be inserted before 1,
// hence the element value should be
// greater than 1 for this recurrence relation
if (arr[i] >= 2)
// Recurrence for dp[val][1]
dp[arr[i]][1] = Math.max(1 + dp[arr[i] - 1][1],
2 + dp[arr[i] - 2][0]);
else
// Maximum length of consecutive sequence
// ending at 1 is equal to 1
dp[arr[i]][1] = 1;
// Update the ans variable with
// the new maximum length possible
ans = Math.max(ans, dp[arr[i]][1]);
}
// Return the ans
return ans;
}
// Driver code
let arr = [ 2, 1, 4, 5 ];
let N = arr.length;
document.write(LongestConsSeq(arr, N));
// This code is contributed by unknown2108
</script>
Producción:
4
Complejidad de tiempo: O(N)
Complejidad de espacio: O(MaxValue) donde MaxValue es el valor máximo presente en la array.