Tutorialspoint.dev

Longest Common Increasing Subsequence (LCS + LIS)

Prerequisites : LCS, LIS

Given two arrays, find length of the longest common increasing subsequence [LCIS] and print one of such sequences (multiple sequences may exist)

Suppose we consider two arrays –
arr1[] = {3, 4, 9, 1} and
arr2[] = {5, 3, 8, 9, 10, 2, 1}

Our answer would be {3, 9} as this is the longest common subsequence which is increasing also.



The idea is to use dynamic programming here as well. We store the longest common increasing sub-sequence ending at each index of arr2[]. We create an auxiliary array table[] such that table[j] stores length of LCIS ending with arr2[j]. At the end, we return maximum value from this table. For filling values in this table, we traverse all elements of arr1[] and for every element arr1[i], we traverse all elements of arr2[]. If we find a match, we update table[j] with length of current LCIS. To maintain current LCIS, we keep checking valid table[j] values.

Below is the program to find length of LCIS.

C++

// A C++ Program to find length of the Longest Common
// Increasing Subsequence (LCIS)
#include<bits/stdc++.h>
using namespace std;
  
// Returns the length and the LCIS of two
// arrays arr1[0..n-1] and arr2[0..m-1]
int LCIS(int arr1[], int n, int arr2[], int m)
{
    // table[j] is going to store length of LCIS
    // ending with arr2[j]. We initialize it as 0,
    int table[m];
    for (int j=0; j<m; j++)
        table[j] = 0;
  
    // Traverse all elements of arr1[]
    for (int i=0; i<n; i++)
    {
        // Initialize current length of LCIS
        int current = 0;
  
        // For each element of arr1[], traverse all
        // elements of arr2[].
        for (int j=0; j<m; j++)
        {
            // If both the array have same elements.
            // Note that we don't break the loop here.
            if (arr1[i] == arr2[j])
                if (current + 1 > table[j])
                    table[j] = current + 1;
  
            /* Now seek for previous smaller common
               element for current element of arr1 */
            if (arr1[i] > arr2[j])
                if (table[j] > current)
                    current = table[j];
        }
    }
  
    // The maximum value in table[] is out result
    int result = 0;
    for (int i=0; i<m; i++)
        if (table[i] > result)
           result = table[i];
  
    return result;
}
  
/* Driver program to test above function */
int main()
{
    int arr1[] = {3, 4, 9, 1};
    int arr2[] = {5, 3, 8, 9, 10, 2, 1};
  
    int n = sizeof(arr1)/sizeof(arr1[0]);
    int m = sizeof(arr2)/sizeof(arr2[0]);
  
    cout << "Length of LCIS is "
         << LCIS(arr1, n, arr2, m);
    return (0);
}

Java

// A Java Program to find length of the Longest
// Common Increasing Subsequence (LCIS)
import java.io.*;
  
class GFG {
  
    // Returns the length and the LCIS of two
    // arrays arr1[0..n-1] and arr2[0..m-1]
    static int LCIS(int arr1[], int n, int arr2[],
                                         int m)
    {
        // table[j] is going to store length of 
        // LCIS ending with arr2[j]. We initialize
        // it as 0,
        int table[] = new int[m];
        for (int j = 0; j < m; j++)
            table[j] = 0;
  
        // Traverse all elements of arr1[]
        for (int i = 0; i < n; i++)
        {
            // Initialize current length of LCIS
            int current = 0;
  
            // For each element of arr1[], trvarse 
            // all elements of arr2[].
            for (int j = 0; j < m; j++)
            {
                // If both the array have same 
                // elements. Note that we don't
                // break the loop here.
                if (arr1[i] == arr2[j])
                    if (current + 1 > table[j])
                        table[j] = current + 1;
  
                /* Now seek for previous smaller
                common element for current 
                element of arr1 */
                if (arr1[i] > arr2[j])
                    if (table[j] > current)
                        current = table[j];
            }
        }
  
        // The maximum value in table[] is out
        // result
        int result = 0;
        for (int i=0; i<m; i++)
            if (table[i] > result)
            result = table[i];
  
        return result;
    }
  
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int arr1[] = {3, 4, 9, 1};
        int arr2[] = {5, 3, 8, 9, 10, 2, 1};
  
        int n = arr1.length;
        int m = arr2.length;
  
    System.out.println("Length of LCIS is " +
                       LCIS(arr1, n, arr2, m));
    }
}
// This code is contributed by Prerna Saini

Python 3

# Python 3 Program to find length of the 
# Longest Common Increasing Subsequence (LCIS)
  
# Returns the length and the LCIS of two
# arrays arr1[0..n-1] and arr2[0..m-1]
def LCIS(arr1, n, arr2, m):
  
    # table[j] is going to store length of LCIS
    # ending with arr2[j]. We initialize it as 0,
    table = [0] * m
    for j in range(m):
        table[j] = 0
  
    # Traverse all elements of arr1[]
    for i in range(n):
      
        # Initialize current length of LCIS
        current = 0
  
        # For each element of arr1[], 
        # traverse all elements of arr2[].
        for j in range(m):
              
            # If both the array have same elements.
            # Note that we don't break the loop here.
            if (arr1[i] == arr2[j]):
                if (current + 1 > table[j]):
                    table[j] = current + 1
  
            # Now seek for previous smaller common
            # element for current element of arr1 
            if (arr1[i] > arr2[j]):
                if (table[j] > current):
                    current = table[j]
  
    # The maximum value in table[] 
    # is out result
    result = 0
    for i in range(m):
        if (table[i] > result):
            result = table[i]
  
    return result
  
# Driver Code
if __name__ == "__main__":
      
    arr1 = [3, 4, 9, 1]
    arr2 = [5, 3, 8, 9, 10, 2, 1]
  
    n = len(arr1)
    m = len(arr2)
  
    print("Length of LCIS is"
           LCIS(arr1, n, arr2, m))
  
# This code is contributed by ita_c

C#

// A C# Program to find length of the Longest
// Common Increasing Subsequence (LCIS)
using System;
  
class GFG {
  
    // Returns the length and the LCIS of two
    // arrays arr1[0..n-1] and arr2[0..m-1]
    static int LCIS(int []arr1, int n,
                    int []arr2, int m)
    {
        // table[j] is going to store length of 
        // LCIS ending with arr2[j]. We initialize
        // it as 0,
        int []table = new int[m];
        for (int j = 0; j < m; j++)
            table[j] = 0;
  
        // Traverse all elements of arr1[]
        for (int i = 0; i < n; i++)
        {
            // Initialize current length of LCIS
            int current = 0;
  
            // For each element of arr1[], trvarse 
            // all elements of arr2[].
            for (int j = 0; j < m; j++)
            {
                // If both the array have same 
                // elements. Note that we don't
                // break the loop here.
                if (arr1[i] == arr2[j])
                    if (current + 1 > table[j])
                        table[j] = current + 1;
  
                /* Now seek for previous smaller
                   common element for current 
                   element of arr1 */
                if (arr1[i] > arr2[j])
                    if (table[j] > current)
                        current = table[j];
            }
        }
  
        // The maximum value in 
        // table[] is out result
        int result = 0;
        for (int i = 0; i < m; i++)
            if (table[i] > result)
            result = table[i];
  
        return result;
    }
  
    /* Driver program to test above function */
    public static void Main()
    {
        int []arr1 = {3, 4, 9, 1};
        int []arr2 = {5, 3, 8, 9, 10, 2, 1};
  
        int n = arr1.Length;
        int m = arr2.Length;
  
    Console.Write("Length of LCIS is " +
                   LCIS(arr1, n, arr2, m));
    }
}
  
// This code is contributed by nitin mittal.

PHP

<?php
// PHP Program to find length of
// the Longest Common Increasing 
// Subsequence (LCIS)
  
// Returns the length and the LCIS 
// of two arrays arr1[0..n-1] and 
// arr2[0..m-1]
function LCIS($arr1, $n, $arr2, $m)
{
    // table[j] is going to store 
    // length of LCIS ending with 
    // arr2[j]. We initialize it as 0,
      
    $table = Array();
      
    //int table[m];
    for ($j = 0; $j < $m; $j++)
        $table[$j] = 0;
  
    // Traverse all elements of arr1[]
    for ($i = 0; $i < $n; $i++)
    {
        // Initialize current
        // length of LCIS
        $current = 0;
  
        // For each element of 
        // arr1[], trvarse all
        // elements of arr2[].
        for ($j = 0; $j < $m; $j++)
        {
            // If both the array have 
            // same elements. Note that
            // we don't break the loop here.
            if ($arr1[$i] == $arr2[$j])
                if ($current + 1 > $table[$j])
                    $table[$j] = $current + 1;
  
            /* Now seek for previous smaller 
            common element for current 
            element of arr1 */
            if ($arr1[$i] > $arr2[$j])
                if ($table[$j] > $current)
                    $current = $table[$j];
        }
    }
  
    // The maximum value in 
    // table[] is out result
    $result = 0;
    for ($i = 0; $i < $m; $i++)
        if ($table[$i] > $result)
        $result = $table[$i];
  
    return $result;
}
  
// Driver Code
$arr1 = array (3, 4, 9, 1);
$arr2 = array (5, 3, 8, 9, 10, 2, 1);
  
$n = sizeof($arr1);
$m = sizeof($arr2);
  
echo "Length of LCIS is ",
       LCIS($arr1, $n, $arr2, $m);
  
// This code is contributed by ajit 
?>


Output :

Length of LCIS is 2

 
How to print a LCIS?
To print the longest common increasing subsequence we keep track of the parent of each element in the longest common increasing subsequence.

C++

// A C++ Program to find length of the Longest Common
// Increasing Subsequence (LCIS)
#include<bits/stdc++.h>
using namespace std;
  
// Returns the length and the LCIS of two
// arrays arr1[0..n-1] and arr2[0..m-1] and
// prints LCIS
int LCIS(int arr1[], int n, int arr2[], int m)
{
    // table[j] is going to store length of LCIS
    // ending with arr2[j]. We initialize it as 0,
    int table[m], parent[m];
    for (int j=0; j<m; j++)
        table[j] = 0;
  
    // Traverse all elements of arr1[]
    for (int i=0; i<n; i++)
    {
        // Initialize current length of LCIS
        int current = 0, last = -1;
  
        // For each element of arr1[], trvarse all
        // elements of arr2[].
        for (int j=0; j<m; j++)
        {
            // If both the array have same elements.
            // Note that we don't break the loop here.
            if (arr1[i] == arr2[j])
            {
                if (current + 1 > table[j])
                {
                    table[j] = current + 1;
                    parent[j] = last;
                }
            }
  
            /* Now seek for previous smaller common
               element for current element of arr1 */
            if (arr1[i] > arr2[j])
            {
                if (table[j] > current)
                {
                    current = table[j];
                    last = j;
                }
            }
        }
    }
  
    // The maximum value in table[] is out result
    int result = 0, index = -1;
    for (int i=0; i<m; i++)
    {
        if (table[i] > result)
        {
           result = table[i];
           index = i;
        }
    }
  
    // LCIS is going to store elements of LCIS
    int lcis[result];
    for (int i=0; index != -1; i++)
    {
        lcis[i] = arr2[index];
        index = parent[index];
    }
  
    cout << "The LCIS is : ";
    for (int i=result-1; i>=0; i--)
        printf ("%d ", lcis[i]);
  
    return result;
}
  
/* Driver program to test above function */
int main()
{
    int arr1[] = {3, 4, 9, 1};
    int arr2[] = {5, 3, 8, 9, 10, 2, 1};
  
    int n = sizeof(arr1)/sizeof(arr1[0]);
    int m = sizeof(arr2)/sizeof(arr2[0]);
  
    cout << " Length of LCIS is "
         << LCIS(arr1, n, arr2, m);
    return (0);
}

Java

// Java Program to find length of the Longest
// Common Increasing Subsequence (LCIS)
import java.io.*;
  
class GFG {
  
    // Returns the length and the LCIS of
    // two arrays arr1[0..n-1] and arr2[0..m-1]
    // and prints LCIS
    static int LCIS(int arr1[], int n, int arr2[],
                                         int m)
    {   
        // table[j] is going to store length of 
        // LCIS ending with arr2[j]. We 
        // initialize it as 0.
        int table[] = new int[m];
        int parent[] = new int[m];
        for (int j = 0; j < m; j++)
            table[j] = 0;
  
        // Traverse all elements of arr1[]
        for (int i = 0; i < n; i++)
        {
            // Initialize current length of LCIS
            int current = 0, last = -1;
  
            // For each element of arr1[],
            // trvarse all elements of arr2[].
            for (int j = 0; j < m; j++)
            {
                // If both the array have same
                // elements. Note that we don't 
                // break the loop here.
                if (arr1[i] == arr2[j])
                {   
                    if (current + 1 > table[j])
                    {
                        table[j] = current + 1;
                        parent[j] = last;
                    }
                }
  
                /* Now seek for previous smaller
                common element for current element
                of arr1 */
                if (arr1[i] > arr2[j])
                {
                    if (table[j] > current)
                    {
                        current = table[j];
                        last = j;
                    }
                }
            }
        }
  
        // The maximum value in table[] is out
        // result
        int result = 0, index = -1;
        for (int i = 0; i < m; i++)
        {
            if (table[i] > result)
            {
            result = table[i];
            index = i;
            }
        }
  
        // LCIS is going to store elements 
        // of LCIS
        int lcis[] = new int[result];
        for (int i = 0; index != -1; i++)
        {
            lcis[i] = arr2[index];
            index = parent[index];
        }
  
        System.out.print("The LCIS is : ");
        for (int i = result - 1; i >= 0; i--)
            System.out.print(lcis[i] + " ");
      
        return result;
    }
  
    /* Driver program to test above function */ 
    public static void main(String[] args)
    {
        int arr1[] = {3, 4, 9, 1};
        int arr2[] = {5, 3, 8, 9, 10, 2, 1};
  
        int n = arr1.length;
        int m = arr2.length;
  
        System.out.println(" Length of LCIS is "+
                          LCIS(arr1, n, arr2, m));
    }
}
// This code is contributed by Prerna Saini

Python3

# A Python3 Program to find length of the 
# Longest Common Increasing Subsequence (LCIS)
  
# Returns the length and the LCIS of two
# arrays arr1[0..n-1] and arr2[0..m-1] and
# prints LCIS
def LCIS(arr1, n, arr2, m):
      
    # table[j] is going to store length of LCIS
    # ending with arr2[j]. We initialize it as 0,
    table = [0 for i in range(m)]
    parent = [0 for i in range(m)]
  
    # Traverse all elements of arr1[]
    for i in range(n):
          
        # Initialize current length of LCIS
        current = 0
        last = -1
  
        # For each element of arr1[], trvarse all
        # elements of arr2[].
        for j in range(m):
              
            # If both the array have same elements.
            # Note that we don't break the loop here.
            if (arr1[i] == arr2[j]):
                if (current + 1 > table[j]):
                    table[j] = current + 1
                    parent[j] = last
                  
            # Now seek for previous smaller common
            # element for current element of arr1 */
            if (arr1[i] > arr2[j]):
                if (table[j] > current):
                    current = table[j]
                    last = j
      
    # The maximum value in table[] is out result
    result = 0
    index = -1
    for i in range(m):
        if (table[i] > result):
            result = table[i]
            index = i
  
    # LCIS is going to store elements of LCIS
    lcis = [0 for i in range(result)]
    i = 0
  
    while(index != -1):
        lcis[i] = arr2[index]
        index = parent[index]
        i += 1
  
    print("The LCIS is : ", end = "")
    for i in range(result - 1,-1,-1):
        print(lcis[i], end = " ")
  
    return result
  
# Driver Code
arr1 = [3, 4, 9, 1]
arr2 = [5, 3, 8, 9, 10, 2, 1]
  
n = len(arr1)
m = len(arr2)
  
print(" Length of LCIS is ",
         LCIS(arr1, n, arr2, m))
  
# This code is contributed by mohit kumar

C#

// C# Program to find length 
// of the Longest Common 
// Increasing Subsequence (LCIS)
using System;
  
class GFG
{
  
// Returns the length and
// the LCIS of two arrays
// arr1[0..n-1] and arr2[0..m-1]
// and prints LCIS
static int LCIS(int []arr1, int n, 
                int []arr2, int m)
    // table[j] is going to store 
    // length of LCIS ending with 
    // arr2[j]. We initialize it as 0.
    int []table = new int[m];
    int []parent = new int[m];
    for (int j = 0; j < m; j++)
        table[j] = 0;
  
    // Traverse all elements of arr1[]
    for (int i = 0; i < n; i++)
    {
        // Initialize current
        // length of LCIS
        int current = 0, last = -1;
  
        // For each element of arr1[],
        // trvarse all elements of arr2[].
        for (int j = 0; j < m; j++)
        {
            // If both the array have same
            // elements. Note that we don't 
            // break the loop here.
            if (arr1[i] == arr2[j])
            
                if (current + 1 > table[j])
                {
                    table[j] = current + 1;
                    parent[j] = last;
                }
            }
  
            /* Now seek for previous 
            smaller common element for 
            current element of arr1 */
            if (arr1[i] > arr2[j])
            {
                if (table[j] > current)
                {
                    current = table[j];
                    last = j;
                }
            }
        }
    }
  
    // The maximum value in 
    // table[] is out result
    int result = 0, index = -1;
    for (int i = 0; i < m; i++)
    {
        if (table[i] > result)
        {
        result = table[i];
        index = i;
        }
    }
  
    // LCIS is going to store 
    // elements of LCIS
    int []lcis = new int[result];
    for (int i = 0; index != -1; i++)
    {
        lcis[i] = arr2[index];
        index = parent[index];
    }
  
    Console.Write("The LCIS is : ");
    for (int i = result - 1; i >= 0; i--)
    Console.Write(lcis[i] + " ");
  
    return result;
}
  
// Driver Code    
static public void Main ()
{
    int []arr1 = {3, 4, 9, 1};
    int []arr2 = {5, 3, 8, 9, 
                  10, 2, 1};
  
    int n = arr1.Length;
    int m = arr2.Length;
  
    Console.WriteLine(" Length of LCIS is "+
                     LCIS(arr1, n, arr2, m));
  
}
}
  
// This code is contributed by ajit

PHP

<?php
// A PHP Program to find 
// length of the Longest
// Common Increasing 
// Subsequence (LCIS)
  
// Returns the length and 
// the LCIS of two arrays 
// arr1[0..n-1] and 
// arr2[0..m-1] and prints LCIS
  
function LCIS($arr1, $n
              $arr2, $m)
{
    // table[j] is going to
    // store length of LCIS
    // ending with arr2[j].
    // We initialize it as 0,
      
    $table = Array(); $parent = Array();
    for ($j = 0; $j < $m; $j++)
        $table[$j] = 0;
  
    // Traverse all
    // elements of arr1[]
    for ($i = 0 ; $i < $n; $i++)
    {
        // Initialize current
        // length of LCIS
        $current = 0; $last = -1;
  
        // For each element of
        // arr1[], trvarse all
        // elements of arr2[].
        for ($j = 0; $j < $m; $j++)
        {
            // If both the array have
            // same elements. Note that 
            // we don't break the loop here.
            if ($arr1[$i] == $arr2[$j])
            {
                if ($current + 1 > $table[$j])
                {
                    $table[$j] = $current + 1;
                    $parent[$j] = $last;
                }
            }
  
            /* Now seek for previous 
            smaller common element for
            current element of arr1 */
            if ($arr1[$i] > $arr2[$j])
            {
                if ($table[$j] > $current)
                {
                    $current = $table[$j];
                    $last = $j;
                }
            }
        }
    }
  
    // The maximum value in
    // table[] is out result
    $result = 0; $index = -1;
    for ($i =0 ; $i < $m; $i++)
    {
        if ($table[$i] > $result)
        {
        $result = $table[$i];
        $index = $i;
        }
    }
  
    // LCIS is going to store 
    // elements of LCIS 
    // $lcis[$result];
    for ($i = 0; $index != -1; $i++)
    {
        $lcis[$i] = $arr2[$index];
        $index = $parent[$index];
    }
  
    echo "The LCIS is : ";
    for ($i = $result - 1; $i >= 0; $i--)
        echo $lcis[$i], " ";
        echo " ";
      
    return $result;
}
  
// Driver Code
$arr1 = array (3, 4, 9, 1);
$arr2 = array (5, 3, 8, 9, 10, 2, 1);
  
$n = sizeof($arr1);
$m = sizeof($arr2);
$x = LCIS($arr1, $n, $arr2, $m);
  
echo "Length of LCIS is ", $x;
      
// This code is contributed by m_kit
?>

Output :

The LCIS is : 3 9 
Length of LCIS is 2

Time Complexity : O(m*n)
Auxiliary Space : O(m)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter