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!
