Dada una secuencia de números en forma de lista enlazada lis . Encuentre la longitud de la subsecuencia creciente más larga (LIS) de la lista enlazada dada.
Ejemplos:
Entrada : lista = 3->10->2->1->20
Salida : 3
Explicación: La subsecuencia creciente más larga es 3->10-> 20Entrada : lista = 3-> 2
Salida : 1
Explicación: Las subsecuencias crecientes más largas son 3 y 2Entrada : lista = 50->3->10->7->40->80
Salida : Longitud de LIS = 4
Explicación: La subsecuencia creciente más larga es {3->7->40->80} o {3- >10->40->80}
Enfoque: la intuición básica de la solución es comenzar a iterar desde el primer Node hasta el final de la lista enlazada. En el proceso de movimiento, calcule la longitud del LIS que termina en cada Node y guárdelo en una variable de conteo . Finalmente, calcule el valor de conteo máximo entre todos los Nodes. Siga los pasos que se mencionan a continuación para resolver el problema:
- Atraviese la lista enlazada desde el Node inicial.
- La longitud LIS de una lista enlazada con un Node es 1. Por lo tanto, inicializamos cada variable de recuento de Nodes en 1 .
- Para cada i-ésimo Node, recorra los primeros (i-1) Nodes y haga lo siguiente:
- si el valor del Node actual es mayor que el valor del Node anterior, extienda la longitud de la secuencia .
- Como se requiere una longitud máxima que termine con el Node actual. seleccione el Node de los primeros (i-1) Nodes que satisfagan la condición anterior y tengan el valor máximo de conteo.
- Una vez que se recorren todos los Nodes siguiendo el procedimiento anterior, encuentre el valor de conteo máximo entre todos los Nodes.
- El valor de conteo máximo es la longitud requerida del LIS .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find LIS on LinkedList
#include <bits/stdc++.h>
using namespace std;
// Structure of a node
class Node {
public:
int data;
struct Node* next;
// "count" variable is to keep track
// of LIS_LENGTH ending with
// that particular element
int count;
};
// Function to find the length of the LIS
int LIS(struct Node* head)
{
// If linked list is empty length is 0
if (head == NULL)
return 0;
// If linked list has only one node
// LIS length is 1
if (head->next == NULL)
return 1;
Node* curr_p = head->next;
// This loop calculates what is
// LIS_LENGTH ending with each and
// every node and stores in
// curr->count variable
while (curr_p != NULL) {
int maxi = 0;
Node* prev_p = head;
// This while loop traverse all nodes
// before curr_p and finds which node
// to extend so that maximum LIS
// length ending with curr_P can be
while (prev_p != curr_p) {
// Only extend if present data
// greater than previous value
if (curr_p->data
> prev_p->data) {
if (prev_p->count > maxi) {
maxi = prev_p->count;
}
}
prev_p = prev_p->next;
}
curr_p->count = 1 + maxi;
curr_p = curr_p->next;
}
int LIS_length = 0;
curr_p = head;
// Finding Maximum LIS_LENGTH
while (curr_p != NULL) {
if (LIS_length < curr_p->count) {
LIS_length = curr_p->count;
}
curr_p = curr_p->next;
}
return LIS_length;
}
// Function to push a node in linked list
void push(struct Node** head_ref,
int new_data)
{
// Allocate node
Node* new_node = new Node();
// Put in the data
new_node->data = new_data;
// Link the old list with the new node
new_node->next = (*head_ref);
// Assign count value to 1
new_node->count = 1;
// Move the head to point the new node
(*head_ref) = new_node;
}
// Driver code
int main()
{
// Start with the empty list
struct Node* head = NULL;
// Create a linked list
// Created linked list will be
// 3->10->2->1->20
push(&head, 20);
push(&head, 1);
push(&head, 2);
push(&head, 10);
push(&head, 3);
// Call LIS function which calculates
// LIS of Linked List
int ans = LIS(head);
cout << ans;
return 0;
}
Java
// Java program to find LIS on LinkedList
import java.util.*;
class GFG{
// Structure of a node
static class Node {
int data;
Node next;
// "count" variable is to keep track
// of LIS_LENGTH ending with
// that particular element
int count;
};
// Function to find the length of the LIS
static int LIS(Node head)
{
// If linked list is empty length is 0
if (head == null)
return 0;
// If linked list has only one node
// LIS length is 1
if (head.next == null)
return 1;
Node curr_p = head.next;
// This loop calculates what is
// LIS_LENGTH ending with each and
// every node and stores in
// curr.count variable
while (curr_p != null) {
int maxi = 0;
Node prev_p = head;
// This while loop traverse all nodes
// before curr_p and finds which node
// to extend so that maximum LIS
// length ending with curr_P can be
while (prev_p != curr_p) {
// Only extend if present data
// greater than previous value
if (curr_p.data
> prev_p.data) {
if (prev_p.count > maxi) {
maxi = prev_p.count;
}
}
prev_p = prev_p.next;
}
curr_p.count = 1 + maxi;
curr_p = curr_p.next;
}
int LIS_length = 0;
curr_p = head;
// Finding Maximum LIS_LENGTH
while (curr_p != null) {
if (LIS_length < curr_p.count) {
LIS_length = curr_p.count;
}
curr_p = curr_p.next;
}
return LIS_length;
}
// Function to push a node in linked list
static Node push(Node head_ref,
int new_data)
{
// Allocate node
Node new_node = new Node();
// Put in the data
new_node.data = new_data;
// Link the old list with the new node
new_node.next = head_ref;
// Assign count value to 1
new_node.count = 1;
// Move the head to point the new node
head_ref = new_node;
return head_ref;
}
// Driver code
public static void main(String[] args)
{
// Start with the empty list
Node head = null;
// Create a linked list
// Created linked list will be
// 3.10.2.1.20
head = push(head, 20);
head = push(head, 1);
head = push(head, 2);
head = push(head, 10);
head = push(head, 3);
// Call LIS function which calculates
// LIS of Linked List
int ans = LIS(head);
System.out.print(ans);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python code for the above approach # Structure of a node class Node: def __init__(self, d): self.data = d self.next = None self.count = 1 # "count" variable is to keep track # of LIS_LENGTH ending with # that particular element # Function to find the length of the LIS def LIS(head): # If linked list is empty length is 0 if (head == None): return 0 # If linked list has only one node # LIS length is 1 if (head.next == None): return 1 curr_p = head.next # This loop calculates what is # LIS_LENGTH ending with each and # every node and stores in # curr.count variable while (curr_p != None): maxi = 0 prev_p = head # This while loop traverse all nodes # before curr_p and finds which node # to extend so that maximum LIS # length ending with curr_P can be while (prev_p != curr_p): # Only extend if present data # greater than previous value if (curr_p.data > prev_p.data): if (prev_p.count > maxi): maxi = prev_p.count prev_p = prev_p.next curr_p.count = 1 + maxi curr_p = curr_p.next LIS_length = 0 curr_p = head # Finding Maximum LIS_LENGTH while (curr_p != None): if (LIS_length < curr_p.count): LIS_length = curr_p.count curr_p = curr_p.next return LIS_length # Driver code # Start with the empty list # Create a linked list # Created linked list will be # 3->10->2->1->20 head = Node(3) head.next = Node(10) head.next.next = Node(2) head.next.next.next = Node(1) head.next.next.next.next = Node(20) # Call LIS function which calculates # LIS of Linked List ans = LIS(head) print(ans) # This code is contributed by Saurabh Jaiswal
C#
// C# program to find LIS on List
using System;
using System.Collections.Generic;
public class GFG {
// Structure of a node
public class Node {
public int data;
public Node next;
// "count" variable is to keep track
// of LIS_LENGTH ending with
// that particular element
public int count;
};
// Function to find the length of the LIS
static int LIS(Node head)
{
// If linked list is empty length is 0
if (head == null)
return 0;
// If linked list has only one node
// LIS length is 1
if (head.next == null)
return 1;
Node curr_p = head.next;
// This loop calculates what is
// LIS_LENGTH ending with each and
// every node and stores in
// curr.count variable
while (curr_p != null) {
int maxi = 0;
Node prev_p = head;
// This while loop traverse all nodes
// before curr_p and finds which node
// to extend so that maximum LIS
// length ending with curr_P can be
while (prev_p != curr_p) {
// Only extend if present data
// greater than previous value
if (curr_p.data > prev_p.data) {
if (prev_p.count > maxi) {
maxi = prev_p.count;
}
}
prev_p = prev_p.next;
}
curr_p.count = 1 + maxi;
curr_p = curr_p.next;
}
int LIS_length = 0;
curr_p = head;
// Finding Maximum LIS_LENGTH
while (curr_p != null) {
if (LIS_length < curr_p.count) {
LIS_length = curr_p.count;
}
curr_p = curr_p.next;
}
return LIS_length;
}
// Function to push a node in linked list
static Node push(Node head_ref, int new_data)
{
// Allocate node
Node new_node = new Node();
// Put in the data
new_node.data = new_data;
// Link the old list with the new node
new_node.next = head_ref;
// Assign count value to 1
new_node.count = 1;
// Move the head to point the new node
head_ref = new_node;
return head_ref;
}
// Driver code
public static void Main(String[] args)
{
// Start with the empty list
Node head = null;
// Create a linked list
// Created linked list will be
// 3.10.2.1.20
head = push(head, 20);
head = push(head, 1);
head = push(head, 2);
head = push(head, 10);
head = push(head, 3);
// Call LIS function which calculates
// LIS of Linked List
int ans = LIS(head);
Console.Write(ans);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript code for the above approach
// Structure of a node
class Node {
constructor(d) {
this.data = d;
this.next = null;
this.count = 1;
}
// "count" variable is to keep track
// of LIS_LENGTH ending with
// that particular element
};
// Function to find the length of the LIS
function LIS(head)
{
// If linked list is empty length is 0
if (head == null)
return 0;
// If linked list has only one node
// LIS length is 1
if (head.next == null)
return 1;
let curr_p = head.next;
// This loop calculates what is
// LIS_LENGTH ending with each and
// every node and stores in
// curr.count variable
while (curr_p != null) {
let maxi = 0;
let prev_p = head;
// This while loop traverse all nodes
// before curr_p and finds which node
// to extend so that maximum LIS
// length ending with curr_P can be
while (prev_p != curr_p) {
// Only extend if present data
// greater than previous value
if (curr_p.data
> prev_p.data) {
if (prev_p.count > maxi) {
maxi = prev_p.count;
}
}
prev_p = prev_p.next;
}
curr_p.count = 1 + maxi;
curr_p = curr_p.next;
}
let LIS_length = 0;
curr_p = head;
// Finding Maximum LIS_LENGTH
while (curr_p != null) {
if (LIS_length < curr_p.count) {
LIS_length = curr_p.count;
}
curr_p = curr_p.next;
}
return LIS_length;
}
// Driver code
// Start with the empty list
// Create a linked list
// Created linked list will be
// 3->10->2->1->20
let head = new Node(3);
head.next = new Node(10);
head.next.next = new Node(2);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(20);
// Call LIS function which calculates
// LIS of Linked List
let ans = LIS(head);
document.write(ans);
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad de tiempo: O(N * N) donde N es la longitud de la lista enlazada
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por abhilashreddy1676 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA