Dados N elementos, escriba un programa que imprima la longitud de 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: 6
Explicación: 3, 4, 5, 6, 7, 8 es la subsecuencia creciente más larga cuyo adyacente elemento difiere en uno.
Entrada: a[] = {6, 7, 8, 3, 4, 5, 9, 10}
Salida: 5
Explicación: 6, 7, 8, 9, 10 es la subsecuencia creciente más larga
Enfoque ingenuo: un enfoque normal será iterar para cada elemento y encontrar la subsecuencia creciente más larga. Para cualquier elemento en particular, encuentre la longitud de la subsecuencia a partir de ese elemento. Imprime la mayor longitud de la subsecuencia así formada. La complejidad temporal de este enfoque será O(n 2 ).
Enfoque de programación dinámica: permita que DP[i] almacene la longitud de la subsecuencia más larga que termina con A[i]. Para cada A[i], si A[i]-1 está presente en la array antes del i-ésimo índice, entonces A[i] se sumará a la subsecuencia creciente que tiene A[i]-1. Por lo tanto, DP[i] = DP[ índice(A[i]-1) ] + 1. Si A[i]-1 no está presente en el arreglo antes del i-ésimo índice, entonces DP[i]=1 ya que el elemento A[i] forma una subsecuencia que comienza con A[i]. Por lo tanto, la relación para DP[i] es:
Si A[i]-1 está presente antes del i-ésimo índice:
- DP[i] = DP[ índice(A[i]-1) ] + 1
más:
- PD[i] = 1
A continuación se muestra la ilustració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
int 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
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
maximum = max(maximum, dp[i]);
}
return maximum;
}
// Driver Code
int main()
{
int a[] = { 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 };
int n = sizeof(a) / sizeof(a[0]);
cout << longestSubsequence(a, n);
return 0;
}
Java
// Java program to find length of the
// longest increasing subsequence
// whose adjacent element differ by 1
import java.util.*;
class lics {
static int LongIncrConseqSubseq(int arr[], int n)
{
// create hashmap to save latest consequent
// number as "key" and its length as "value"
HashMap<Integer, Integer> map = new HashMap<>();
// put first element as "key" and its length as "value"
map.put(arr[0], 1);
for (int i = 1; i < n; i++) {
// check if last consequent of arr[i] exist or not
if (map.containsKey(arr[i] - 1)) {
// put the updated consequent number
// and increment its value(length)
map.put(arr[i], map.get(arr[i] - 1) + 1);
// remove the last consequent number
map.remove(arr[i] - 1);
}
// if their is no last consequent of
// arr[i] then put arr[i]
else {
map.put(arr[i], 1);
}
}
return Collections.max(map.values());
}
// driver code
public static void main(String args[])
{
// Take input from user
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = sc.nextInt();
System.out.println(LongIncrConseqSubseq(arr, n));
}
}
// This code is contributed by CrappyDoctor
Python3
# python program to find length of the # longest increasing subsequence # whose adjacent element differ by 1 from collections import defaultdict import sys # function that returns the length of the # longest increasing subsequence # whose adjacent element differ by 1 def longestSubsequence(a, n): mp = defaultdict(lambda:0) # stores the length of the longest # subsequence that ends with a[i] dp = [0 for i in range(n)] maximum = -sys.maxsize # iterate for all element 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 maximum = max(maximum, dp[i]) return maximum # Driver Code a = [3, 10, 3, 11, 4, 5, 6, 7, 8, 12] n = len(a) print(longestSubsequence(a, n)) # This code is contributed by Shrikant13
C#
// C# program to find length of the
// longest increasing subsequence
// whose adjacent element differ by 1
using System;
using System.Collections.Generic;
class GFG{
static int longIncrConseqSubseq(int []arr,
int n)
{
// Create hashmap to save
// latest consequent number
// as "key" and its length
// as "value"
Dictionary<int,
int> map = new Dictionary<int,
int>();
// Put first element as "key"
// and its length as "value"
map.Add(arr[0], 1);
for (int i = 1; i < n; i++)
{
// Check if last consequent
// of arr[i] exist or not
if (map.ContainsKey(arr[i] - 1))
{
// put the updated consequent number
// and increment its value(length)
map.Add(arr[i], map[arr[i] - 1] + 1);
// Remove the last consequent number
map.Remove(arr[i] - 1);
}
// If their is no last consequent of
// arr[i] then put arr[i]
else
{
if(!map.ContainsKey(arr[i]))
map.Add(arr[i], 1);
}
}
int max = int.MinValue;
foreach(KeyValuePair<int,
int> entry in map)
{
if(entry.Value > max)
{
max = entry.Value;
}
}
return max;
}
// Driver code
public static void Main(String []args)
{
// Take input from user
int []arr = {3, 10, 3, 11,
4, 5, 6, 7, 8, 12};
int n = arr.Length;
Console.WriteLine(longIncrConseqSubseq(arr, n));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program to find length of the
// longest increasing subsequence
// whose adjacent element differ by 1
// 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
var mp = new Map();
// stores the length of the longest
// subsequence that ends with a[i]
var dp = Array(n).fill(0);
var maximum = -1000000000;
// iterate for all element
for (var i = 0; i < n; i++) {
// if a[i]-1 is present before i-th index
if (mp.has(a[i] - 1)) {
// last index of a[i]-1
var 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
maximum = Math.max(maximum, dp[i]);
}
return maximum;
}
// Driver Code
var a = [3, 10, 3, 11, 4, 5, 6, 7, 8, 12];
var n = a.length;
document.write( longestSubsequence(a, n));
</script>
6
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar : O(N), ya que estamos usando espacio extra para dp y map m .