Dada una array de n enteros positivos. Necesitamos encontrar la mayor secuencia creciente de enteros positivos consecutivos.
Ejemplos:
Input : arr[] = {5, 7, 6, 7, 8}
Output : Size of LIS = 4
LIS = 5, 6, 7, 8
Input : arr[] = {5, 7, 8, 7, 5}
Output : Size of LIS = 2
LIS = 7, 8
Este problema se puede resolver fácilmente mediante el concepto de LIS , donde cada siguiente elemento mayor difiere del anterior en 1. Pero esto requerirá una complejidad de tiempo O (n ^ 2).
Con el uso de hashing podemos encontrar el tamaño de la secuencia creciente más larga con enteros consecutivos en complejidad temporal de O(n).
Creamos una tabla hash. Ahora, para cada elemento arr[i], realizamos hash[arr[i]] = hash[arr[i] – 1] + 1. Entonces, para cada elemento conocemos el final de subsecuencia creciente consecutivo más largo con eso. Finalmente devolvemos el valor máximo de la tabla hash.
Implementación:
C++
// C++ implementation of longest continuous increasing
// subsequence
#include <bits/stdc++.h>
using namespace std;
// Function for LIS
int findLIS(int A[], int n)
{
unordered_map<int, int> hash;
// Initialize result
int LIS_size = 1;
int LIS_index = 0;
hash[A[0]] = 1;
// iterate through array and find
// end index of LIS and its Size
for (int i = 1; i < n; i++) {
hash[A[i]] = hash[A[i] - 1] + 1;
if (LIS_size < hash[A[i]]) {
LIS_size = hash[A[i]];
LIS_index = A[i];
}
}
// print LIS size
cout << "LIS_size = " << LIS_size << "\n";
// print LIS after setting start element
cout << "LIS : ";
int start = LIS_index - LIS_size + 1;
while (start <= LIS_index) {
cout << start << " ";
start++;
}
}
// driver
int main()
{
int A[] = { 2, 5, 3, 7, 4, 8, 5, 13, 6 };
int n = sizeof(A) / sizeof(A[0]);
findLIS(A, n);
return 0;
}
Java
// Java implementation of longest continuous increasing
// subsequence
import java.util.*;
class GFG
{
// Function for LIS
static void findLIS(int A[], int n)
{
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
// Initialize result
int LIS_size = 1;
int LIS_index = 0;
hash.put(A[0], 1);
// iterate through array and find
// end index of LIS and its Size
for (int i = 1; i < n; i++)
{
hash.put(A[i], hash.get(A[i] - 1)==null? 1:hash.get(A[i] - 1)+1);
if (LIS_size < hash.get(A[i]))
{
LIS_size = hash.get(A[i]);
LIS_index = A[i];
}
}
// print LIS size
System.out.println("LIS_size = " + LIS_size);
// print LIS after setting start element
System.out.print("LIS : ");
int start = LIS_index - LIS_size + 1;
while (start <= LIS_index)
{
System.out.print(start + " ");
start++;
}
}
// Driver code
public static void main(String[] args)
{
int A[] = { 2, 5, 3, 7, 4, 8, 5, 13, 6 };
int n = A.length;
findLIS(A, n);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of longest
# continuous increasing subsequence
# Function for LIS
def findLIS(A, n):
hash = dict()
# Initialize result
LIS_size, LIS_index = 1, 0
hash[A[0]] = 1
# iterate through array and find
# end index of LIS and its Size
for i in range(1, n):
# If the desired key is not present
# in dictionary, it will throw key error,
# to avoid this error this is necessary
if A[i] - 1 not in hash:
hash[A[i] - 1] = 0
hash[A[i]] = hash[A[i] - 1] + 1
if LIS_size < hash[A[i]]:
LIS_size = hash[A[i]]
LIS_index = A[i]
# print LIS size
print("LIS_size =", LIS_size)
# print LIS after setting start element
print("LIS : ", end = "")
start = LIS_index - LIS_size + 1
while start <= LIS_index:
print(start, end = " ")
start += 1
# Driver Code
if __name__ == "__main__":
A = [ 2, 5, 3, 7, 4, 8, 5, 13, 6 ]
n = len(A)
findLIS(A, n)
# This code is contributed by sanjeev2552
C#
// C# implementation of longest continuous increasing
// subsequence
using System;
using System.Collections.Generic;
class GFG
{
// Function for LIS
static void findLIS(int []A, int n)
{
Dictionary<int,int> hash = new Dictionary<int,int>();
// Initialize result
int LIS_size = 1;
int LIS_index = 0;
hash.Add(A[0], 1);
// iterate through array and find
// end index of LIS and its Size
for (int i = 1; i < n; i++)
{
if(hash.ContainsKey(A[i]-1))
{
var val = hash[A[i]-1];
hash.Remove(A[i]);
hash.Add(A[i], val + 1);
}
else
{
hash.Add(A[i], 1);
}
if (LIS_size < hash[A[i]])
{
LIS_size = hash[A[i]];
LIS_index = A[i];
}
}
// print LIS size
Console.WriteLine("LIS_size = " + LIS_size);
// print LIS after setting start element
Console.Write("LIS : ");
int start = LIS_index - LIS_size + 1;
while (start <= LIS_index)
{
Console.Write(start + " ");
start++;
}
}
// Driver code
public static void Main(String[] args)
{
int []A = { 2, 5, 3, 7, 4, 8, 5, 13, 6 };
int n = A.Length;
findLIS(A, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of longest continuous increasing
// subsequence
// Function for LIS
function findLIS(A, n) {
let hash = new Map();
// Initialize result
let LIS_size = 1;
let LIS_index = 0;
hash.set(A[0], 1);
// iterate through array and find
// end index of LIS and its Size
for (let i = 1; i < n; i++) {
hash.set(A[i], hash.get(A[i] - 1) == null ?
1 : hash.get(A[i] - 1) + 1);
if (LIS_size < hash.get(A[i])) {
LIS_size = hash.get(A[i]);
LIS_index = A[i];
}
}
// print LIS size
document.write("LIS_size = " + LIS_size + "<br>");
// print LIS after setting start element
document.write("LIS : ");
let start = LIS_index - LIS_size + 1;
while (start <= LIS_index) {
document.write(start + " ");
start++;
}
}
// Driver code
let A = [2, 5, 3, 7, 4, 8, 5, 13, 6];
let n = A.length;
findLIS(A, n);
// This code is contributed by gfgking
</script>
LIS_size = 5 LIS : 2 3 4 5 6
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi . 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 review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA