Dados n elementos, escriba un programa que imprima la subsecuencia creciente más larga cuya diferencia de elementos adyacentes sea uno.
Ejemplos:
Entrada: a[] = {3, 10, 3, 11, 4, 5, 6, 7, 8, 12}
Salida: 3 4 5 6 7 8
Explicación: 3, 4, 5, 6, 7, 8 es el subsecuencia creciente más larga cuyo elemento adyacente difiere en uno.
Entrada: a[] = {6, 7, 8, 3, 4, 5, 9, 10}
Salida: 6 7 8 9 10
Explicación: 6, 7, 8, 9, 10 es la subsecuencia creciente más larga
Hemos discutido cómo encontrar la longitud de la subsecuencia consecutiva creciente más larga . Para imprimir la subsecuencia, almacenamos el índice del último elemento. Luego imprimimos elementos consecutivos que terminan con el último elemento.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find length of the
// longest increasing subsequence
// whose adjacent element differ by 1
#include <bits/stdc++.h>
using namespace std;
// function that returns the length of the
// longest increasing subsequence
// whose adjacent element differ by 1
void longestSubsequence(int a[], int n)
{
// stores the index of elements
unordered_map<int, int> mp;
// stores the length of the longest
// subsequence that ends with a[i]
int dp[n];
memset(dp, 0, sizeof(dp));
int maximum = INT_MIN;
// iterate for all element
int index = -1;
for (int i = 0; i < n; i++) {
// if a[i]-1 is present before i-th index
if (mp.find(a[i] - 1) != mp.end()) {
// last index of a[i]-1
int lastIndex = mp[a[i] - 1] - 1;
// relation
dp[i] = 1 + dp[lastIndex];
}
else
dp[i] = 1;
// stores the index as 1-index as we need to
// check for occurrence, hence 0-th index
// will not be possible to check
mp[a[i]] = i + 1;
// stores the longest length
if (maximum < dp[i]) {
maximum = dp[i];
index = i;
}
}
// We know last element of sequence is
// a[index]. We also know that length
// of subsequence is "maximum". So We
// print these many consecutive elements
// starting from "a[index] - maximum + 1"
// to a[index].
for (int curr = a[index] - maximum + 1;
curr <= a[index]; curr++)
cout << curr << " ";
}
// Driver Code
int main()
{
int a[] = { 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 };
int n = sizeof(a) / sizeof(a[0]);
longestSubsequence(a, n);
return 0;
}
Java
// Java program to find length of the
// longest increasing subsequence
// whose adjacent element differ by
import java.util.HashMap;
class GFG
{
// function that returns the length of the
// longest increasing subsequence
// whose adjacent element differ by 1
public static void longestSubsequence(int[] a,
int n)
{
// stores the index of elements
HashMap<Integer,
Integer> mp = new HashMap<>();
// stores the length of the longest
// subsequence that ends with a[i]
int[] dp = new int[n];
int maximum = Integer.MIN_VALUE;
// iterate for all element
int index = -1;
for(int i = 0; i < n; i++)
{
// if a[i]-1 is present before i-th index
if (mp.get(a[i] - 1) != null)
{
// last index of a[i]-1
int lastIndex = mp.get(a[i] - 1) - 1;
// relation
dp[i] = 1 + dp[lastIndex];
}
else
dp[i] = 1;
// stores the index as 1-index as we need to
// check for occurrence, hence 0-th index
// will not be possible to check
mp.put(a[i], i + 1);
// stores the longest length
if (maximum < dp[i])
{
maximum = dp[i];
index = i;
}
}
// We know last element of sequence is
// a[index]. We also know that length
// of subsequence is "maximum". So We
// print these many consecutive elements
// starting from "a[index] - maximum + 1"
// to a[index].
for (int curr = a[index] - maximum + 1;
curr <= a[index]; curr++)
System.out.print(curr + " ");
}
// Driver Code
public static void main(String[] args)
{
int[] a = { 3, 10, 3, 11, 4,
5, 6, 7, 8, 12 };
int n = a.length;
longestSubsequence(a, n);
}
}
// This code is contributed by sanjeev2552
Python3
# Python 3 program to find length of
# the longest increasing subsequence
# whose adjacent element differ by 1
import sys
# function that returns the length
# of the longest increasing subsequence
# whose adjacent element differ by 1
def longestSubsequence(a, n):
# stores the index of elements
mp = {i:0 for i in range(13)}
# stores the length of the longest
# subsequence that ends with a[i]
dp = [0 for i in range(n)]
maximum = -sys.maxsize - 1
# iterate for all element
index = -1
for i in range(n):
# if a[i]-1 is present before
# i-th index
if ((a[i] - 1 ) in mp):
# last index of a[i]-1
lastIndex = mp[a[i] - 1] - 1
# relation
dp[i] = 1 + dp[lastIndex]
else:
dp[i] = 1
# stores the index as 1-index as we
# need to check for occurrence, hence
# 0-th index will not be possible to check
mp[a[i]] = i + 1
# stores the longest length
if (maximum < dp[i]):
maximum = dp[i]
index = i
# We know last element of sequence is
# a[index]. We also know that length
# of subsequence is "maximum". So We
# print these many consecutive elements
# starting from "a[index] - maximum + 1"
# to a[index].
for curr in range(a[index] - maximum + 1,
a[index] + 1, 1):
print(curr, end = " ")
# Driver Code
if __name__ == '__main__':
a = [3, 10, 3, 11, 4, 5,
6, 7, 8, 12]
n = len(a)
longestSubsequence(a, n)
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to find length of the
// longest increasing subsequence
// whose adjacent element differ by
using System;
using System.Collections.Generic;
class GFG
{
// function that returns the length of the
// longest increasing subsequence
// whose adjacent element differ by 1
static void longestSubsequence(int[] a, int n)
{
// stores the index of elements
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// stores the length of the longest
// subsequence that ends with a[i]
int[] dp = new int[n];
int maximum = -100000000;
// iterate for all element
int index = -1;
for(int i = 0; i < n; i++)
{
// if a[i]-1 is present before i-th index
if (mp.ContainsKey(a[i] - 1) == true)
{
// last index of a[i]-1
int lastIndex = mp[a[i] - 1] - 1;
// relation
dp[i] = 1 + dp[lastIndex];
}
else
dp[i] = 1;
// stores the index as 1-index as we need to
// check for occurrence, hence 0-th index
// will not be possible to check
mp[a[i]] = i + 1;
// stores the longest length
if (maximum < dp[i])
{
maximum = dp[i];
index = i;
}
}
// We know last element of sequence is
// a[index]. We also know that length
// of subsequence is "maximum". So We
// print these many consecutive elements
// starting from "a[index] - maximum + 1"
// to a[index].
for (int curr = a[index] - maximum + 1;
curr <= a[index]; curr++)
Console.Write(curr + " ");
}
// Driver Code
static void Main()
{
int[] a = { 3, 10, 3, 11, 4,
5, 6, 7, 8, 12 };
int n = a.Length;
longestSubsequence(a, n);
}
}
// This code is contributed by mohit kumar
Javascript
<script>
// Javascript program to find length of the
// longest increasing subsequence
// whose adjacent element differ by
// function that returns the length of the
// longest increasing subsequence
// whose adjacent element differ by 1
function longestSubsequence(a, n)
{
// stores the index of elements
let mp = new Map();
// stores the length of the longest
// subsequence that ends with a[i]
let dp = new Array(n);
let maximum = Number.MIN_VALUE;
// iterate for all element
let index = -1;
for(let i = 0; i < n; i++)
{
// if a[i]-1 is present before i-th index
if (mp.get(a[i] - 1) != null)
{
// last index of a[i]-1
let lastIndex = mp.get(a[i] - 1) - 1;
// relation
dp[i] = 1 + dp[lastIndex];
}
else
dp[i] = 1;
// stores the index as 1-index as we need to
// check for occurrence, hence 0-th index
// will not be possible to check
mp.set(a[i], i + 1);
// stores the longest length
if (maximum < dp[i])
{
maximum = dp[i];
index = i;
}
}
// We know last element of sequence is
// a[index]. We also know that length
// of subsequence is "maximum". So We
// print these many consecutive elements
// starting from "a[index] - maximum + 1"
// to a[index].
for (let curr = a[index] - maximum + 1;
curr <= a[index]; curr++)
document.write(curr + " ");
}
// Driver Code
let a=[3, 10, 3, 11, 4,
5, 6, 7, 8, 12 ];
let n = a.length;
longestSubsequence(a, n);
// This code is contributed by patel2127
</script>
Producción:
3 4 5 6 7 8
Complejidad de tiempo: O(n), ya que estamos usando un bucle para recorrer n veces y en cada recorrido.
Espacio auxiliar: O(n), ya que estamos usando espacio adicional para dp y mp .