Longest Increasing Subsequence using Longest Common Subsequence Algorithm

0 0 10 minutes read

Given an array arr[] of N integers, the task is to find and print the Longest Increasing Subsequence.
Examples:

Input: arr[] = {12, 34, 1, 5, 40, 80}
Output: 4
{12, 34, 40, 80} and {1, 5, 40, 80} are the
longest increasing subsequences.
Input: arr[] = {10, 22, 9, 33, 21, 50, 41, 60, 80}
Output: 6

Prerequisite: LCS, LIS
Approach: The longest increasing subsequence of any sequence is the subsequence of the sorted sequence of itself. It can be solved using a Dynamic Programming approach. The approach is the same as the classical LCS problem but instead of the second sequence, given sequence is taken again in its sorted form.
Note: We should remove all duplicates otherwise it might give wrong result. For example in {1, 1, 1} we know the longest increasing subsequence(a1 < a2 < … ak) is of length 1, but if we try out this example in LIS using LCS method we would get 3 (because it finds the longest common subsequence).
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
//function to return size of array without duplicates
int removeDuplicates(vector<int> &arr)
{
    int k = 0;
    for (int i = 1; i < arr.size(); i++)
    {
        if (arr[i] != arr[k]) {
            arr[++k] = arr[i];
        }
    }
    return k + 1;
}
// Function to return the size of the
// longest increasing subsequence
int LISusingLCS(vector<int>& seq)
{
    int n = seq.size();
 
    // Create an 2D array of integer
    // for tabulation
    vector<vector<int> > L(n + 1, vector<int>(n + 1));
 
    // Take the second sequence as the sorted
    // sequence of the given sequence
    vector<int> sortedseq(seq);
 
    sort(sortedseq.begin(), sortedseq.end());
    //remove duplicates
      int m = removeDuplicates(sortedseq)
    // Classical Dynamic Programming algorithm
    // for Longest Common Subsequence
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
 
            else if (seq[i - 1] == sortedseq[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
 
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }
 
    // Return the ans
    return L[n][m];
}
 
// Driver code
int main()
{
 
    vector<int> sequence{ 12, 34, 1, 5, 40, 80 };
 
    cout << LISusingLCS(sequence) << endl;
 
    return 0;
}

Java

//Java implementation of above approach
import java.util.*;
 
class GFG
{
     
// Function to return the size of the
// longest increasing subsequence
static int LISusingLCS(Vector<Integer> seq)
{
    int n = seq.size();
 
    // Create an 2D array of integer
    // for tabulation
    int L[][] = new int [n + 1][n + 1];
 
    // Take the second sequence as the sorted
    // sequence of the given sequence
    Vector<Integer> sortedseq = new Vector<Integer>(seq);
 
    Collections.sort(sortedseq);
 
    // Classical Dynamic Programming algorithm
    // for Longest Common Subsequence
    for (int i = 0; i <= n; i++) 
    {
        for (int j = 0; j <= n; j++) 
        {
            if (i == 0 || j == 0)
                L[i][j] = 0;
 
            else if (seq.get(i - 1) == sortedseq.get(j - 1))
                L[i][j] = L[i - 1][j - 1] + 1;
 
            else
                L[i][j] = Math.max(L[i - 1][j], 
                                   L[i][j - 1]);
        }
    }
 
    // Return the ans
    return L[n][n];
}
 
// Driver code
public static void main(String args[])
{
    Vector<Integer> sequence = new Vector<Integer>();
    sequence.add(12);
    sequence.add(34);
    sequence.add(1);
    sequence.add(5);
    sequence.add(40);
    sequence.add(80);
 
    System.out.println(LISusingLCS(sequence));
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation of the approach
 
# Function to return the size of the
# longest increasing subsequence
def LISusingLCS(seq):
    n = len(seq)
 
    # Create an 2D array of integer
    # for tabulation
    L = [[0 for i in range(n + 1)] 
            for i in range(n + 1)]
     
    # Take the second sequence as the sorted
    # sequence of the given sequence
    sortedseq = sorted(seq)
 
    # Classical Dynamic Programming algorithm
    # for Longest Common Subsequence
    for i in range(n + 1):
        for j in range(n + 1):
            if (i == 0 or j == 0):
                L[i][j] = 0
 
            elif (seq[i - 1] == sortedseq[j - 1]):
                L[i][j] = L[i - 1][j - 1] + 1
 
            else:
                L[i][j] = max(L[i - 1][j], 
                              L[i][j - 1])
 
    # Return the ans
    return L[n][n]
 
# Driver code
sequence = [12, 34, 1, 5, 40, 80]
 
print(LISusingLCS(sequence))
 
# This code is contributed by mohit kumar

C#

// C# implementation of above approach
using System;
using System.Collections.Generic;
 
class GFG
{
     
// Function to return the size of the
// longest increasing subsequence
static int LISusingLCS(List<int> seq)
{
    int n = seq.Count;
 
    // Create an 2D array of integer
    // for tabulation
    int [,]L = new int [n + 1, n + 1];
 
    // Take the second sequence as the sorted
    // sequence of the given sequence
    List<int> sortedseq = new List<int>(seq);
 
    sortedseq.Sort();
 
    // Classical Dynamic Programming algorithm
    // for longest Common Subsequence
    for (int i = 0; i <= n; i++) 
    {
        for (int j = 0; j <= n; j++) 
        {
            if (i == 0 || j == 0)
                L[i, j] = 0;
 
            else if (seq[i - 1] == sortedseq[j - 1])
                L[i, j] = L[i - 1, j - 1] + 1;
 
            else
                L[i,j] = Math.Max(L[i - 1, j], 
                                L[i, j - 1]);
        }
    }
 
    // Return the ans
    return L[n, n];
}
 
// Driver code
public static void Main(String []args)
{
    List<int> sequence = new List<int>();
    sequence.Add(12);
    sequence.Add(34);
    sequence.Add(1);
    sequence.Add(5);
    sequence.Add(40);
    sequence.Add(80);
 
    Console.WriteLine(LISusingLCS(sequence));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
//Javascript implementation of above approach
 
// Function to return the size of the
// longest increasing subsequence
function LISusingLCS(seq)
{
    let n = seq.length;
  
    // Create an 2D array of integer
    // for tabulation
    let L = new Array(n + 1);
    for(let i = 0; i < (n + 1); i++)
    {
        L[i] = new Array(n + 1);
        for(let j = 0; j < (n + 1); j++)
        {
            L[i][j] = 0;
        }
    }
  
    // Take the second sequence as the sorted
    // sequence of the given sequence
    let sortedseq =[...seq];
  
    sortedseq.sort(function(a,b){return a-b;});
    // Classical Dynamic Programming algorithm
    // for Longest Common Subsequence
    for (let i = 0; i <= n; i++)
    {
        for (let j = 0; j <= n; j++)
        {
            if (i == 0 || j == 0)
                L[i][j] = 0;
  
            else if (seq[i - 1] == sortedseq[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
  
            else
                L[i][j] = Math.max(L[i - 1][j],
                                   L[i][j - 1]);
        }
    }
  
    // Return the ans
    return L[n][n];
}
 
// Driver code
let sequence = [12, 34, 1, 5, 40, 80];
document.write(LISusingLCS(sequence));
 
// This code is contributed by patel2127
</script>

Output:

Time Complexity: O(n²) where n is the length of the sequence
Auxiliary Space: O(n²)

Efficient approach: Space Optimization

In previous approach the current value i.e. L[i][j] is depend no the current and previous row values. So to optimize the space complexity we can only keep track of the current and previous values of L[j] instead of the entire 2D array. This reduces the space complexity to O(n) instead of O(n^2).

Implementation Steps:

Create a vector L of size n+1 to store the values of the Longest Increasing Subsequence.
Create a copy of the original sequence called sortedseq and sort it in descending order and remove duplicates.
Use a nested for-loop, where the outer loop iterates through i from 1 to n and the inner loop iterates through j from 1 to m.
Use two variables prev and curr to store the left and top values of the current cell L[i][j].
If seq[i-1] and sortedseq[j-1] are equal, update L[j] with prev+1. else update L[j] with max(L[j], L[j-1]).
Update prev to curr at the end of each inner loop iteration.
Return the value at L[m] as the Longest Increasing Subsequence.

Implementation:

C++

// C++ implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
 
//function to return size of array without duplicates
int removeDuplicates(vector<int> &arr)
{
    int k = 0;
    for (int i = 1; i < arr.size(); i++)
    {
        if (arr[i] != arr[k]) {
            arr[++k] = arr[i];
        }
    }
    return k + 1;
}
 
// Function to return the size of the
// longest increasing subsequence
int LISusingLCS(vector<int>& seq)
{
    int n = seq.size();
   
      // Create an veector of integer
      // to store values
    vector<int> L(n + 1);
     
      // Take the second sequence as the sorted
    // sequence of the given sequence
    vector<int> sortedseq(seq);
   
   
    sort(sortedseq.begin(), sortedseq.end());
   
      //remove duplicates
    int m = removeDuplicates(sortedseq);
     
      // Classical Dynamic Programming algorithm
    // for Longest Common Subsequence
    for (int i = 1; i <= n; i++) {
        int prev = 0;
        for (int j = 1; j <= m; j++) {
            int curr = L[j];
            if (seq[i - 1] == sortedseq[j - 1])
                L[j] = prev + 1;
            else
                L[j] = max(L[j], L[j - 1]);
            prev = curr;
        }
    }
     
      // Return the answer
    return L[m];
}
     
// Driver code
int main()
{
    vector<int> sequence{ 12, 34, 1, 5, 40, 80 };
      // function call
    cout << LISusingLCS(sequence) << endl;
    return 0;
}

Java

// Java code addition 
import java.io.*;
import java.util.*;
 
// Function to return size of array without duplicates
class GFG{
  public static int removeDuplicates(int[] arr) {
    int k = 0;
    for (int i = 1; i < arr.length; i++) {
      if (arr[i] != arr[k]) {
        arr[++k] = arr[i];
      }
    }
    return k + 1;
  }
 
  // Function to return the size of the longest increasing subsequence
  public static int LISusingLCS(int[] seq) {
    int n = seq.length;
 
    // Create an array of integer to store values
    int[] L = new int[n + 1];
 
    // Take the second sequence as the sorted sequence of the given sequence
    int[] sortedseq = seq.clone();
 
    Arrays.sort(sortedseq);
 
    // Remove duplicates
    int m = removeDuplicates(sortedseq);
 
    // Classical Dynamic Programming algorithm for Longest Common Subsequence
    for (int i = 1; i <= n; i++) {
      int prev = 0;
      for (int j = 1; j <= m; j++) {
        int curr = L[j];
        if (seq[i - 1] == sortedseq[j - 1])
          L[j] = prev + 1;
        else
          L[j] = Math.max(L[j], L[j - 1]);
        prev = curr;
      }
    }
 
    // Return the answer
    return L[m];
  }
 
  // Driver code
  public static void main(String[] args) {
    int[] sequence = {12, 34, 1, 5, 40, 80};
    // Function call
    System.out.println(LISusingLCS(sequence));
  }
 
}
 
// The code is contributed by Nidhi goel. 

Python3

# Python implementation of the approach
 
# function to return size of array without duplicates
def removeDuplicates(arr):
    k = 0
    for i in range(1, len(arr)):
        if arr[i] != arr[k]:
            k += 1
            arr[k] = arr[i]
    return k + 1
 
# Function to return the size of the
# longest increasing subsequence
def LISusingLCS(seq):
    n = len(seq)
   
    # Create a list of integer to store values
    L = [0] * (n + 1)
 
    # Take the second sequence as the sorted
    # sequence of the given sequence
    sortedseq = sorted(seq)
 
    # remove duplicates
    m = removeDuplicates(sortedseq)
 
    # Classical Dynamic Programming algorithm
    # for Longest Common Subsequence
    for i in range(1, n + 1):
        prev = 0
        for j in range(1, m + 1):
            curr = L[j]
            if seq[i - 1] == sortedseq[j - 1]:
                L[j] = prev + 1
            else:
                L[j] = max(L[j], L[j - 1])
            prev = curr
 
    # Return the answer
    return L[m]
     
# Driver code
if __name__ == '__main__':
    sequence = [12, 34, 1, 5, 40, 80]
     
    # function call
    print(LISusingLCS(sequence))

C#

using System;
using System.Linq;
 
// Function to return size of array without duplicates
class GFG {
    public static int RemoveDuplicates(int[] arr)
    {
        int k = 0;
        for (int i = 1; i < arr.Length; i++) {
            if (arr[i] != arr[k]) {
                arr[++k] = arr[i];
            }
        }
        return k + 1;
    }
 
    // Function to return the size of the longest increasing
    // subsequence
    public static int LISusingLCS(int[] seq)
    {
        int n = seq.Length;
 
        // Create an array of integer to store values
        int[] L = new int[n + 1];
 
        // Take the second sequence as the sorted sequence
        // of the given sequence
        int[] sortedseq = seq.Clone() as int[];
 
        Array.Sort(sortedseq);
 
        // Remove duplicates
        int m = RemoveDuplicates(sortedseq);
 
        // Classical Dynamic Programming algorithm for
        // Longest Common Subsequence
        for (int i = 1; i <= n; i++) {
            int prev = 0;
            for (int j = 1; j <= m; j++) {
                int curr = L[j];
                if (seq[i - 1] == sortedseq[j - 1])
                    L[j] = prev + 1;
                else
                    L[j] = Math.Max(L[j], L[j - 1]);
                prev = curr;
            }
        }
 
        // Return the answer
        return L[m];
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int[] sequence = { 12, 34, 1, 5, 40, 80 };
        // Function call
        Console.WriteLine(LISusingLCS(sequence));
    }
}

Javascript

// Function to return size of array without duplicates
function removeDuplicates(arr) {
    let k = 0;
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] != arr[k]) {
            arr[++k] = arr[i];
        }
    }
    return k + 1;
}
 
// Function to return the size of the longest increasing subsequence
function LISusingLCS(seq) {
    let n = seq.length;
 
    // Create an array of integer to store values
    let L = new Array(n + 1).fill(0);
 
    // Take the second sequence as the sorted sequence of the given sequence
    let sortedseq = [...seq];
 
    sortedseq.sort((a, b) => a - b);
 
    // Remove duplicates
    let m = removeDuplicates(sortedseq);
 
    // Classical Dynamic Programming algorithm for Longest Common Subsequence
    for (let i = 1; i <= n; i++) {
        let prev = 0;
        for (let j = 1; j <= m; j++) {
            let curr = L[j];
            if (seq[i - 1] == sortedseq[j - 1])
                L[j] = prev + 1;
            else
                L[j] = Math.max(L[j], L[j - 1]);
            prev = curr;
        }
    }
 
    // Return the answer
    return L[m];
}
 
// Driver code
let sequence = [12, 34, 1, 5, 40, 80];
// Function call
console.log(LISusingLCS(sequence));

Output

Time Complexity: O(n^2) where n is the length of the sequence
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 zambiatek!