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
// 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); } } |
Python3
# 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#
// 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 |
Javascript
<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> |
Output:
3
Time Complexity: O(N3)
Auxiliary Space: O(N3)
Related Topic: Subarrays, Subsequences, and Subsets in Array
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!
