Length of the longest increasing subsequence which does not contain a given sequence as Subarray
Last Updated : 11 Jul, 2022
Given two arrays arr[] and arr1[] of lengths N and M respectively, the task is to find the longest increasing subsequence of array arr[] such that it does not contain array arr1[] as subarray.
Examples:
Input: arr[] = {5, 3, 9, 3, 4, 7}, arr1[] = {3, 3, 7}
Output: 4
Explanation: Required longest increasing subsequence is {3, 3, 4, 7}.
Input: arr[] = {1, 2, 3}, arr1[] = {1, 2, 3}
Output: 2
Explanation: Required longest increasing subsequence is {1, 2}.
Naive Approach: The simplest approach is to generate all possible subsequences of the given array and print the length of the longest subsequence among them, which does not contain arr1[] as subarray.
Time Complexity: O(M * 2N) where N and M are the lengths of the given arrays.
Auxiliary Space: O(M + N)
Efficient Approach: The idea is to use lps[] array generated using KMP Algorithm and Dynamic Programming to find the longest non-decreasing subsequence without any subarray equals to sequence[]. Follow the below steps to solve the problem:
- Initialize an array dp[N][N][N] where dp[i][j][K] stores the maximum length of non-decreasing subsequence up to index i where j is the index of the previously chosen element in the array arr[] and K denotes that the currently found sequence contains subarray sequence[0, K].
- Also, generate an array to store the length of the longest prefix suffix using KMP Algorithm.
- The maximum length can be found by memoizing the below dp transitions:
dp(i, prev, k) = max(1 + dp(i + 1, i, k2), dp(i + 1, prev, k)) where,
- i is the current index.
- prev is the previously chosen element.
- k2 is index of prefix subarray included so far in the currently found sequence which can be found using KMP Array for longest prefix suffix.
Base Case:
- If k is equals to the length of the given sequence, return as the currently found subsequence contains the arr1[].
- If i reaches N, return as no more elements exist.
- If the current state has already been calculated, return.
Below is the implementation of the above approach:
C++ // C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Initialize dp and KMP array int dp[6][6][6]; int KMPArray[2]; // Length of the given sequence[] int m; // Function to find the max-length // subsequence that does not have // subarray sequence[] int findSubsequence(int a[], int sequence[], int i, int prev, int k, int al, int sl) { // Stores the subsequence // explored so far if (k == m) return INT_MIN; // Base Case if (i == al) return 0; // Using memoization to // avoid re-computation if (prev != -1 && dp[i][prev][k] != -1) { return dp[i][prev][k]; } int include = 0; if (prev == -1 || a[i] >= a[prev]) { int k2 = k; // Using KMP array to find // corresponding index in arr1[] while (k2 > 0 && a[i] != sequence[k2]) k2 = KMPArray[k2 - 1]; // Incrementing k2 as we are // including this element in // the subsequence if (a[i] == sequence[k2]) k2++; // Possible answer for // current state include = 1 + findSubsequence( a, sequence, i + 1, i, k2, al, sl); } // Maximum answer for // current state int ans = max( include, findSubsequence( a, sequence, i + 1, prev, k, al, sl)); // Memoizing the answer for // the corresponding state if (prev != -1) { dp[i][prev][k] = ans; } // Return the answer for // current state return ans; } // Function that generate KMP Array void fillKMPArray(int pattern[]) { // Previous longest prefix suffix int j = 0; int i = 1; // KMPArray[0] is a always 0 KMPArray[0] = 0; // The loop calculates KMPArray[i] // for i = 1 to M - 1 while (i < m) { // If current character is // same if (pattern[i] == pattern[j]) { j++; // Update the KMP array KMPArray[i] = j; i++; } // Otherwise else { // Update the KMP array if (j != 0) j = KMPArray[j - 1]; else { KMPArray[i] = j; i++; } } } } // Function to print the maximum // possible length void printAnswer(int a[], int sequence[], int al, int sl) { // Length of the given sequence m = sl; // Generate KMP array fillKMPArray(sequence); // Initialize the states to -1 memset(dp, -1, sizeof(dp)); // Get answer int ans = findSubsequence(a, sequence, 0, -1, 0, al, sl); // Print answer cout << ((ans < 0) ? 0 : ans) << endl; } // Driver code int main() { // Given array int arr[] = { 5, 3, 9, 3, 4, 7 }; // Give arr1 int arr1[] = { 3, 4 }; // Function Call printAnswer(arr, arr1, 6, 2); return 0; } // This code is contributed by divyeshrabadiya07. // Java program for the above approach import java.io.*; import java.util.*; class GFG { // Initialize dp and KMP array static int[][][] dp; static int[] KMPArray; // Length of the given sequence[] static int m; // Function to find the max-length // subsequence that does not have // subarray sequence[] private static int findSubsequence( int[] a, int[] sequence, int i, int prev, int k) { // Stores the subsequence // explored so far if (k == m) return Integer.MIN_VALUE; // Base Case if (i == a.length) return 0; // Using memoization to // avoid re-computation if (prev != -1 && dp[i][prev][k] != -1) { return dp[i][prev][k]; } int include = 0; if (prev == -1 || a[i] >= a[prev]) { int k2 = k; // Using KMP array to find // corresponding index in arr1[] while (k2 > 0 && a[i] != sequence[k2]) k2 = KMPArray[k2 - 1]; // Incrementing k2 as we are // including this element in // the subsequence if (a[i] == sequence[k2]) k2++; // Possible answer for // current state include = 1 + findSubsequence( a, sequence, i + 1, i, k2); } // Maximum answer for // current state int ans = Math.max( include, findSubsequence( a, sequence, i + 1, prev, k)); // Memoizing the answer for // the corresponding state if (prev != -1) { dp[i][prev][k] = ans; } // Return the answer for // current state return ans; } // Function that generate KMP Array private static void fillKMPArray(int[] pattern) { // Previous longest prefix suffix int j = 0; int i = 1; // KMPArray[0] is a always 0 KMPArray[0] = 0; // The loop calculates KMPArray[i] // for i = 1 to M - 1 while (i < m) { // If current character is // same if (pattern[i] == pattern[j]) { j++; // Update the KMP array KMPArray[i] = j; i++; } // Otherwise else { // Update the KMP array if (j != 0) j = KMPArray[j - 1]; else { KMPArray[i] = j; i++; } } } } // Function to print the maximum // possible length static void printAnswer( int a[], int sequence[]) { // Length of the given sequence m = sequence.length; // Initialize kmp array KMPArray = new int[m]; // Generate KMP array fillKMPArray(sequence); // Initialize dp dp = new int[a.length][a.length][a.length]; // Initialize the states to -1 for (int i = 0; i < a.length; i++) for (int j = 0; j < a.length; j++) Arrays.fill(dp[i][j], -1); // Get answer int ans = findSubsequence( a, sequence, 0, -1, 0); // Print answer System.out.println((ans < 0) ? 0 : ans); } // Driver code public static void main(String[] args) throws Exception { // Given array int[] arr = { 5, 3, 9, 3, 4, 7 }; // Give arr1 int[] arr1 = { 3, 4 }; // Function Call printAnswer(arr, arr1); } } # Python program for the above approach # Initialize dp and KMP array from pickle import GLOBAL import sys dp = [[[-1 for i in range(6)]for j in range(6)]for k in range(6)] KMPArray = [0 for i in range(2)] # Length of the given sequence[] m = 0 # Function to find the max-length # subsequence that does not have # subarray sequence[] def findSubsequence(a, sequence, i,prev, k, al, sl): global KMPArray global dp # Stores the subsequence # explored so far if (k == m): return -sys.maxsize -1 # Base Case if (i == al): return 0 # Using memoization to # avoid re-computation if (prev != -1 and dp[i][prev][k] != -1): return dp[i][prev][k] include = 0 if (prev == -1 or a[i] >= a[prev]): k2 = k # Using KMP array to find # corresponding index in arr1[] while (k2 > 0 and a[i] != sequence[k2]): k2 = KMPArray[k2 - 1] # Incrementing k2 as we are # including this element in # the subsequence if (a[i] == sequence[k2]): k2 += 1 # Possible answer for # current state include = 1 + findSubsequence( a, sequence, i + 1, i, k2, al, sl) # Maximum answer for # current state ans = max(include, findSubsequence( a, sequence, i + 1, prev, k, al, sl)) # Memoizing the answer for # the corresponding state if (prev != -1) : dp[i][prev][k] = ans # Return the answer for # current state return ans # Function that generate KMP Array def fillKMPArray(pattern): global m global KMPArray # Previous longest prefix suffix j = 0 i = 1 # KMPArray[0] is a always 0 KMPArray[0] = 0 # The loop calculates KMPArray[i] # for i = 1 to M - 1 while (i < m): # If current character is # same if (pattern[i] == pattern[j]): j += 1 # Update the KMP array KMPArray[i] = j i += 1 # Otherwise else: # Update the KMP array if (j != 0): j = KMPArray[j - 1] else: KMPArray[i] = j i += 1 # Function to print the maximum # possible length def printAnswer(a, sequence, al, sl): global m # Length of the given sequence m = sl # Generate KMP array fillKMPArray(sequence) # Get answer ans = findSubsequence(a, sequence, 0, -1, 0, al, sl) # Print answer if(ans < 0): print(0) else : print(ans) # Driver code # Given array arr = [ 5, 3, 9, 3, 4, 7 ] # Give arr1 arr1 = [ 3, 4 ] # Function Call printAnswer(arr, arr1, 6, 2) # This code is contributed by shinjanpatra
// C# program for the above approach using System; using System.Collections; using System.Collections.Generic; class GFG{ // Initialize dp and KMP array static int[,,] dp; static int[] KMPArray; // Length of the given sequence[] static int m; // Function to find the max-length // subsequence that does not have // subarray sequence[] private static int findSubsequence(int[] a, int[] sequence, int i, int prev, int k) { // Stores the subsequence // explored so far if (k == m) return int.MinValue; // Base Case if (i == a.Length) return 0; // Using memoization to // avoid re-computation if (prev != -1 && dp[i, prev, k] != -1) { return dp[i, prev, k]; } int include = 0; if (prev == -1 || a[i] >= a[prev]) { int k2 = k; // Using KMP array to find // corresponding index in arr1[] while (k2 > 0 && a[i] != sequence[k2]) k2 = KMPArray[k2 - 1]; // Incrementing k2 as we are // including this element in // the subsequence if (a[i] == sequence[k2]) k2++; // Possible answer for // current state include = 1 + findSubsequence(a, sequence, i + 1, i, k2); } // Maximum answer for // current state int ans = Math.Max(include, findSubsequence(a, sequence, i + 1, prev, k)); // Memoizing the answer for // the corresponding state if (prev != -1) { dp[i, prev, k] = ans; } // Return the answer for // current state return ans; } // Function that generate KMP Array private static void fillKMPArray(int[] pattern) { // Previous longest prefix suffix int j = 0; int i = 1; // KMPArray[0] is a always 0 KMPArray[0] = 0; // The loop calculates KMPArray[i] // for i = 1 to M - 1 while (i < m) { // If current character is // same if (pattern[i] == pattern[j]) { j++; // Update the KMP array KMPArray[i] = j; i++; } // Otherwise else { // Update the KMP array if (j != 0) j = KMPArray[j - 1]; else { KMPArray[i] = j; i++; } } } } // Function to print the maximum // possible length static void printAnswer(int[] a, int[] sequence) { // Length of the given sequence m = sequence.Length; // Initialize kmp array KMPArray = new int[m]; // Generate KMP array fillKMPArray(sequence); // Initialize dp dp = new int[a.Length, a.Length, a.Length]; // Initialize the states to -1 for(int i = 0; i < a.Length; i++) for(int j = 0; j < a.Length; j++) for(int k = 0; k < a.Length; k++) dp[i, j, k] = -1; // Get answer int ans = findSubsequence(a, sequence, 0, -1, 0); // Print answer Console.WriteLine((ans < 0) ? 0 : ans); } // Driver code public static void Main() { // Given array int[] arr = { 5, 3, 9, 3, 4, 7 }; // Give arr1 int[] arr1 = { 3, 4 }; // Function Call printAnswer(arr, arr1); } } // This code is contributed by akhilsaini <script> // JavaScript program to implement above approach // Initialize dp and KMP array let dp = new Array(6).fill(-1).map(()=>new Array(6).fill(-1).map(()=>new Array(6).fill(-1))); let KMPArray = new Array(2); // Length of the given sequence let m; // Function to find the max-length // subsequence that does not have // subarray sequence[] function findSubsequence(a, sequence, i,prev, k, al, sl) { // Stores the subsequence // explored so far if (k == m) return Number.MIN_VALUE; // Base Case if (i == al) return 0; // Using memoization to // avoid re-computation if (prev != -1 && dp[i][prev][k] != -1) { return dp[i][prev][k]; } let include = 0; if (prev == -1 || a[i] >= a[prev]) { let k2 = k; // Using KMP array to find // corresponding index in arr1[] while (k2 > 0 && a[i] != sequence[k2]) k2 = KMPArray[k2 - 1]; // Incrementing k2 as we are // including this element in // the subsequence if (a[i] == sequence[k2]) k2++; // Possible answer for // current state include = 1 + findSubsequence( a, sequence, i + 1, i, k2, al, sl); } // Maximum answer for // current state let ans = Math.max( include, findSubsequence( a, sequence, i + 1, prev, k, al, sl)); // Memoizing the answer for // the corresponding state if (prev != -1) { dp[i][prev][k] = ans; } // Return the answer for // current state return ans; } // Function that generate KMP Array function fillKMPArray(pattern) { // Previous longest prefix suffix let j = 0; let i = 1; // KMPArray[0] is a always 0 KMPArray[0] = 0; // The loop calculates KMPArray[i] // for i = 1 to M - 1 while (i < m) { // If current character is // same if (pattern[i] == pattern[j]) { j++; // Update the KMP array KMPArray[i] = j; i++; } // Otherwise else { // Update the KMP array if (j != 0) j = KMPArray[j - 1]; else { KMPArray[i] = j; i++; } } } } // Function to print the maximum // possible length function printAnswer(a, sequence, al, sl) { // Length of the given sequence m = sl; // Generate KMP array fillKMPArray(sequence); // Get answer let ans = findSubsequence(a, sequence, 0, -1, 0, al, sl); // Print answer console.log((ans < 0) ? 0 : ans); } // Driver code // Given array let arr = [ 5, 3, 9, 3, 4, 7 ]; // Give arr1 let arr1 = [ 3, 4 ]; // Function Call printAnswer(arr, arr1, 6, 2); // This code is contributed by shinjanpatra </script> Time Complexity: O(N3)
Auxiliary Space: O(N3)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Similar Reads
Longest increasing subsequence which forms a subarray in the sorted representation of the array Given an array arr[] of N integers, the task is to find the length of the longest increasing subsequence such that it forms a subarray when the original array is sorted. Examples: Input: arr[] = { 2, 6, 4, 8, 2, 9 }Output: 3Explanation: Sorted array: {2, 2, 4, 6, 8, 9}All possible non-decreasing seq
11 min read
Check if a non-contiguous subsequence same as the given subarray exists or not Given an array arr[] consisting of N integers and two integer values L and R, indicating the starting and ending indices of a subarray, the task is to check if there exists a non-contiguous subsequence which is same as the given subarray or not. If found to be true, print "Yes". Otherwise, print "No
7 min read
Length of longest increasing prime subsequence from a given array Given an array arr[] consisting of N positive integers, the task is to find the length of the longest increasing subsequence consisting of Prime Numbers in the given array. Examples: Input: arr[] = {1, 2, 5, 3, 2, 5, 1, 7}Output: 4Explanation:The Longest Increasing Prime Subsequence is {2, 3, 5, 7}.
9 min read
Length of the longest increasing subsequence such that no two adjacent elements are coprime Given an array arr[]. The task is to find the length of the longest Subsequence from the given array such that the sequence is strictly increasing and no two adjacent elements are coprime. Note: The elements in the given array are strictly increasing in order (1 <= a[i] <= 105)Examples: Input
9 min read
Maximize sum of all elements which are not a part of the Longest Increasing Subsequence Given an array arr[] of integers, find the maximum possible sum of all elements that are not part of a Longest Increasing Subsequence (LIS) of the array.If there are multiple LIS of the same length, choose the one whose elements have the smallest sum, so that the sum of the remaining (non-LIS) eleme
14 min read
Find the length of Longest increasing Consecutive Subarray Given an array arr[] of N integers, the task is to find the length of the longest increasing subarray such that elements in the subarray are consecutive integers. Examples: Input: arr[] = {1, 9, 3, 4, 20, 2}Output: 2Explanation: The subarray {3, 4} is the longest subarray of consecutive elements Inp
4 min read