Longest Increasing Subsequence(LIS) using two arrays
Given two arrays A[] and B[] of size N. Your Task is to find Longest Increasing Subsequence(LIS) in another array C[] such that array C[] is formed by following rules:
- C[i] = A[i] or C[i] = B[i] for all i from 1 to N.
Examples:
Input: A[] = {2, 3, 1}, B[] = {1, 2, 1}
Output: 2
Explanation: Form C[] as following:
- For i = 1, we have two choices A[1] = 2 and B[1] = 1 for C. Pick from array B[]. C[1] = B[1] = 1
- For i = 2, we have two choices A[2] = 3 and B[2] = 2 for C. Pick from array B[]. C[2] = B[2] = 2
- For i = 3, we have two choices A[3] = 1 and B[3] = 1 for C. Pick from array A[]. C[3] = A[3] = 1
Finally, C[] formed is {1, 2, 1} which has Longest Increasing Subsequence of size 2.
Input: A[] = {1, 3, 2, 1}, B[] = {2, 2, 3, 4}
Output: 4
Explanation: Form C[] as following:
- For i = 1, we have two choices A[1] = 1 and B[1] = 2 for C. Pick from array A[]. C[1] = A[1] = 1
- For i = 2, we have two choices A[2] = 3 and B[2] = 2 for C. Pick from array B[]. C[2] = B[2] = 2
- For i = 3, we have two choices A[3] = 2 and B[3] = 3 for C. Pick from array B[]. C[3] = B[3] = 3
- For i = 4, we have two choices A[4] = 1 and B[4] = 4 for C. Pick from array B[]. C[4] = B[4] = 4
Finally, C[] formed is {1, 2, 3, 4} which has Longest Increasing subsequence of size 4.
Approach: To solve the problem, follow the below idea:
Dynamic Programming can be used to solve this problem.
dp[i][0] represents the Longest Increasing Subsequence till index i if we pick ith element from array A[]
dp[i][1] represents the Longest Increasing Subsequence till index i if we pick ith element from array B[]Recurrence Relation:
- dp[i][0] = max(dp[i][0], dp[i – 1][0] + 1) (if i’th element of A[] is greater than (i-1)th element of A[])
- dp[i][0] = max(dp[i][0] , dp[i – 1][1] + 1) (if i’th element of A[] is greater than (i-1)th element of B[])
- dp[i][1] = max(dp[i][1], dp[i – 1][0] + 1) (if i’th element of B[] is greater than (i-1)th element of A[])
- dp[i][1] = max(dp[i][1], dp[i – 1][1] + 1) (if i’th element of B[] is greater than (i-1)th element of B[])
Step-by-step algorithm:
- Declaring dp[N][2] array initialized with zero.
- Iterate i from 1 to N – 1 and for each iteration follow given steps:
- if A[i] is greater than A[i – 1] update dp[i][0] as dp[i – 1][0] + 1
- if A[i] is greater than B[i – 1] update dp[i][0] as max(dp[i][0], dp[i – 1][1] + 1)
- if B[i] is greater than A[i – 1] update dp[i][1] as dp[i – 1][0] + 1
- if B[i] is greater than B[i – 1] update dp[i][1] as max(dp[i][1], dp[i – 1][1] + 1)
- Declare variable ans set to 0
- Iterate over all indexes and update ans as max({ans, dp[i][0], dp[i][1]})
- After iterating over all the indices, return ans.
Below is the implementation of the above approach:
C++
// C++ code #include <bits/stdc++.h> using namespace std; // Function to Longest Strictly increasing subsequence by // choosing elements from two arrays int findLIS( int A[], int B[], int N) { // Declare dp array vector<vector< int > > dp(N + 1, vector< int >(2, 0)); // calculate maximum LIS formed ending at i'th index for ( int i = 1; i < N; i++) { // if i'th element of A is greater than (i-1)th // element of A if (A[i] > A[i - 1]) dp[i][0] = max(dp[i][0], dp[i - 1][0] + 1); // if i'th element of A is greater than (i - 1)th // element of B if (A[i] > B[i - 1]) dp[i][0] = max(dp[i][0], dp[i - 1][1] + 1); // if i'th element of B is greater than (i - 1)th // element of A if (B[i] > A[i - 1]) dp[i][1] = max(dp[i][1], dp[i - 1][0] + 1); // if i'th element of B is greater than (i - 1)th // element of B if (B[i] > B[i - 1]) dp[i][1] = max(dp[i][1], dp[i - 1][1] + 1); } // calculate maximum length int ans = 0; // maximum LIS formed at each index for ( int i = 0; i < N; i++) ans = max({ ans, dp[i][0], dp[i][1] }); // return answer return ans + 1; } // Driver Code int main() { // Input int N = 3; int A[] = { 2, 3, 1 }, B[] = { 1, 2, 1 }; // Function Call cout << findLIS(A, B, N) << endl; return 0; } |
Java
// Java Implementation import java.util.Arrays; public class LongestIncreasingSubsequence { public static int findLIS( int [] A, int [] B, int N) { // Declare dp array int [][] dp = new int [N + 1 ][ 2 ]; // calculate maximum LIS formed ending at i'th index for ( int i = 1 ; i < N; i++) { // if i'th element of A is greater than (i-1)th // element of A if (A[i] > A[i - 1 ]) dp[i][ 0 ] = Math.max(dp[i][ 0 ], dp[i - 1 ][ 0 ] + 1 ); // if i'th element of A is greater than (i - 1)th // element of B if (A[i] > B[i - 1 ]) dp[i][ 0 ] = Math.max(dp[i][ 0 ], dp[i - 1 ][ 1 ] + 1 ); // if i'th element of B is greater than (i - 1)th // element of A if (B[i] > A[i - 1 ]) dp[i][ 1 ] = Math.max(dp[i][ 1 ], dp[i - 1 ][ 0 ] + 1 ); // if i'th element of B is greater than (i - 1)th // element of B if (B[i] > B[i - 1 ]) dp[i][ 1 ] = Math.max(dp[i][ 1 ], dp[i - 1 ][ 1 ] + 1 ); } // calculate maximum length int ans = 0 ; // maximum LIS formed at each index for ( int i = 0 ; i < N; i++) ans = Math.max(ans, Math.max(dp[i][ 0 ], dp[i][ 1 ])); // return answer return ans + 1 ; } public static void main(String[] args) { // Input int N = 3 ; int [] A = { 2 , 3 , 1 }; int [] B = { 1 , 2 , 1 }; // Function Call System.out.println(findLIS(A, B, N)); } } // This code is contributed by Sakshi |
Python3
# Python code # Function to Longest Strictly increasing subsequence by # choosing elements from two arrays def findLIS(A, B, N): # Declare dp array dp = [[ 0 , 0 ] for _ in range (N + 1 )] # calculate maximum LIS formed ending at i'th index for i in range ( 1 , N): # if i'th element of A is greater than (i-1)th # element of A if A[i] > A[i - 1 ]: dp[i][ 0 ] = max (dp[i][ 0 ], dp[i - 1 ][ 0 ] + 1 ) # if i'th element of A is greater than (i - 1)th # element of B if A[i] > B[i - 1 ]: dp[i][ 0 ] = max (dp[i][ 0 ], dp[i - 1 ][ 1 ] + 1 ) # if i'th element of B is greater than (i - 1)th # element of A if B[i] > A[i - 1 ]: dp[i][ 1 ] = max (dp[i][ 1 ], dp[i - 1 ][ 0 ] + 1 ) # if i'th element of B is greater than (i - 1)th # element of B if B[i] > B[i - 1 ]: dp[i][ 1 ] = max (dp[i][ 1 ], dp[i - 1 ][ 1 ] + 1 ) # calculate maximum length ans = 0 # maximum LIS formed at each index for i in range (N): ans = max (ans, dp[i][ 0 ], dp[i][ 1 ]) # return answer return ans + 1 # Driver Code if __name__ = = "__main__" : # Input N = 3 A = [ 2 , 3 , 1 ] B = [ 1 , 2 , 1 ] # Function Call print (findLIS(A, B, N)) |
C#
using System; class Program { // Function to Longest Strictly increasing subsequence by // choosing elements from two arrays static int FindLIS( int [] A, int [] B, int N) { // Declare dp array int [][] dp = new int [N + 1][]; for ( int i = 0; i <= N; i++) { dp[i] = new int [2]; } // calculate maximum LIS formed ending at i'th index for ( int i = 1; i < N; i++) { // if i'th element of A is greater than (i-1)th // element of A if (A[i] > A[i - 1]) dp[i][0] = Math.Max(dp[i][0], dp[i - 1][0] + 1); // if i'th element of A is greater than (i - 1)th // element of B if (A[i] > B[i - 1]) dp[i][0] = Math.Max(dp[i][0], dp[i - 1][1] + 1); // if i'th element of B is greater than (i - 1)th // element of A if (B[i] > A[i - 1]) dp[i][1] = Math.Max(dp[i][1], dp[i - 1][0] + 1); // if i'th element of B is greater than (i - 1)th // element of B if (B[i] > B[i - 1]) dp[i][1] = Math.Max(dp[i][1], dp[i - 1][1] + 1); } // calculate maximum length int ans = 0; // maximum LIS formed at each index for ( int i = 0; i < N; i++) ans = Math.Max(ans, Math.Max(dp[i][0], dp[i][1])); // return answer return ans + 1; } // Driver Code static void Main() { // Input int N = 3; int [] A = { 2, 3, 1 }; int [] B = { 1, 2, 1 }; // Function Call Console.WriteLine(FindLIS(A, B, N)); } } // This code is contributed by rambabuguphka |
Javascript
// JavaScript code // Function to find Longest Strictly increasing subsequence by // choosing elements from two arrays function findLIS(A, B, N) { // Declare dp array let dp = new Array(N + 1).fill(0).map(() => new Array(2).fill(0)); // calculate maximum LIS formed ending at i'th index for (let i = 1; i < N; i++) { // if i'th element of A is greater than (i-1)th // element of A if (A[i] > A[i - 1]) dp[i][0] = Math.max(dp[i][0], dp[i - 1][0] + 1); // if i'th element of A is greater than (i - 1)th // element of B if (A[i] > B[i - 1]) dp[i][0] = Math.max(dp[i][0], dp[i - 1][1] + 1); // if i'th element of B is greater than (i - 1)th // element of A if (B[i] > A[i - 1]) dp[i][1] = Math.max(dp[i][1], dp[i - 1][0] + 1); // if i'th element of B is greater than (i - 1)th // element of B if (B[i] > B[i - 1]) dp[i][1] = Math.max(dp[i][1], dp[i - 1][1] + 1); } // calculate maximum length let ans = 0; // maximum LIS formed at each index for (let i = 0; i < N; i++) ans = Math.max(ans, dp[i][0], dp[i][1]); // return answer return ans + 1; } // Driver Code let N = 3; let A = [2, 3, 1], B = [1, 2, 1]; // Function Call console.log(findLIS(A, B, N)); // This code is contributed by shivamgupta0987654321 |
2
Time Complexity: O(N), where N is the size of input array A[] or B[].
Auxiliary Space: O(N)
Contact Us