Skip to main content

Longest Increasing Subsequence in given Linked List

Given a sequence of numbers in the form of a linked list lis. Find the length of the Longest Increasing Subsequence(LIS) of the given Linked List.

Examples:

Input:  list = 3->10->2->1->20
Output: 3
Explanation: The longest increasing subsequence is 3->10-> 20

Input:  list = 3-> 2
Output: 1
Explanation: The longest increasing subsequence are 3 and 2

Input: list = 50->3->10->7->40->80
Output: Length of LIS = 4
Explanation: The longest increasing subsequence is 3->7->40->80 or 3->10->40->80

 

Approach: The basic intuition of the solution is to start iterating from the first node to the end of linked list .In the process of moving calculate length of LIS ending at every node and store it in a count variable. Finally, calculate maximum count value among all nodes. Follow the steps mentioned below to solve the problem: 

  • Traverse the linked list from the starting node.
    • LIS length of  a  linked list with one node is 1 .So we initialize  every node count variable to 1.
    • For every ith node traverse the first (i-1) nodes and do the following:
      • if value of current node is greater than the value of previous node, extend  sequence length.
      • As maximum length ending with current  node is required. select node from first (i-1) nodes which satisfy the previous condition and have maximum count value .
  • Once all the nodes are traversed following the above procedure .find maximum count value among all nodes.
  • The maximum count value is the required length of the LIS.

Below is the implementation of the above approach:

C++




// C++ program to find LIS on LinkedList
#include
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

















 






 




 



































































 
 


Output

3




 


Time Complexity: O(N * N) where N is the length of the linked list
Auxiliary Space: O(N)


 








                                            Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.

                                            Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!







 

https://neveropen.tech/longest-increasing-subsequence-in-given-linked-list/?feed_id=138&_unique_id=683d282a3367b












Labels:





























Comments











Post a Comment



















Popular posts from this blog





















Bare Metal Billing Client Portal Guide




























      Contents   Order a Bare Metal Server  My Custom / Contract Pricing   View Contract Details   Location Management      Order History & Status   View Order Details         Introduction  The phoenixNAP Client Portal allows you to purchase bare metal servers  and other phoenixNAP products and services. Using the intuitive interface and its essential tools, you can also easily manage your infrastructure.  This quick guide will show you how to use the new form  to order a bare metal server and how to navigate through new bare metal features  within the phoenixNAP Client Portal.     Order a Bare Metal Server  An order form is an accordion-based process for purchasing phoenixNAP products. Our order form allows you to view the pricing and order multiple products from the same category at the same time.     Note:  The prices on the form are per month . A contract is not required. However, if you want a contracted price, you may be eligible for a discount  depending on the quantity and ...




















Post a Comment









Read more






























Find pair of integers such that their sum is twice their Bitwise XOR




























   Given a positive integer N, the task is to find all pairs of integers  (i, j)  from the range [1, N]  in increasing order of i  such that:   1 ? i, j ? N  i + j = N  i + j = 2*(i ^ j)  If there are no such pairs, return a pair -1, -1.   Note:  Here ‘^’  denotes the bitwise  XOR  operation.   Examples:   Input: N = 4 Output: 1, 3, 3, 1 Explanation: A total of 3 pairs satisfy the first condition: (1, 3), (2, 2), (3, 1). There are only two valid pairs out of them: (1, 3) and (3, 1) as 1 + 3 = 4 = 2 * (1 ^ 3).    Input: 7 Output: -1, -1  Input: 144 Output: 36, 108,  44, 100, 100, 44,  108, 36    Approach:      The problem can be viewed as a bitwise manipulation problem satisfying pre-conditions.   If the pairs add upto N  then it is obvious that the second element j  of the pair can be generated using the first element  i as  j = N – i . Then we just have to check for the remaining condition   i + j = 2 * (i ^ j).   Follow the steps mentioned below to solve the problem:   Traverse from ...




















Post a Comment









Read more






























Add an element in Array  to make the bitwise XOR as K




























   Given an array arr[]  containing N positive integers, the task is to add an integer such that the bitwise Xor of the new array becomes K.  Examples:    Input: arr[] = 1, 4, 5, 6, K = 4 Output: 2 Explanation: Bit-wise XOR of the array is 6.  And bit-wise XOR of 6 and 2 is 4.  Input: arr[] = 2, 7, 9, 1, K = 5 Output:  8        Approach: The solution to the problem is based on the following idea of bitwise Xor:   If for two numbers X  and Y , the bitwise Xor of X and Y is Z  then the bitwise Xor of X and Z is Y.   Follow the steps to solve the problem:   Let the bitwise XOR of the array elements be X .   Say the required value to be added is Y  such that X Xor Y = K .  From the above observation, it is clear that the value to be added (Y) is the same as X Xor K .   Below is the implementation of the above approach:   C++                                 // C++ code to implement the above approach     #include  using  namespace  std;     // Function to find the required value  int  find_...




















Post a Comment









Read more