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 duplicatesint 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 subsequenceint 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 codeint main(){ vector<int> sequence{ 12, 34, 1, 5, 40, 80 }; cout << LISusingLCS(sequence) << endl; return 0;} |
Java
//Java implementation of above approachimport java.util.*;class GFG{ // Function to return the size of the// longest increasing subsequencestatic 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 codepublic 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 subsequencedef 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 codesequence = [12, 34, 1, 5, 40, 80]print(LISusingLCS(sequence))# This code is contributed by mohit kumar |
C#
// C# implementation of above approachusing System;using System.Collections.Generic;class GFG{ // Function to return the size of the// longest increasing subsequencestatic 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 codepublic 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 subsequencefunction 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 codelet sequence = [12, 34, 1, 5, 40, 80];document.write(LISusingLCS(sequence));// This code is contributed by patel2127</script> |
Output:
4
Time Complexity: O(n2) where n is the length of the sequence
Auxiliary Space: O(n2)
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 duplicatesint 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 subsequenceint 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 codeint 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 duplicatesclass 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 duplicatesdef 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 subsequencedef 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 codeif __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 duplicatesclass 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 duplicatesfunction 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 subsequencefunction 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 codelet sequence = [12, 34, 1, 5, 40, 80];// Function callconsole.log(LISusingLCS(sequence)); |
Output
4
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
