Longest Prefix Subsequence matching Fibonacci Sequence
Given an array arr of size N. Also, there is another array B of the infinite size where B[0] = B[1] = 1, and for all (i >= 2), B[i] = B[i-1]+B[i-2], the task is to find the length of the longest subsequence which is the prefix of array B. If there is no subsequence which is the prefix of array B then return 0.
Examples:
Input: N = 6, arr = {1, 2, 3, 1, 2, 3}
Output: 4
Explanation: Subsequence {1,1,2,3} which is a prefix array of B of length 4.Input: N = 5, arr = {2, 3, 1, 2, 5}
Output: 1
Explanation: Subsequence {1} which is a prefix array of B of length 1.
Approach: To solve the problem follow the below idea:
Using Dynamic Programming, we can iterate over both the arrays A and B, and see the total common length until A length is finished.
Below are the steps involved:
- Create an array dp as B of length A where each element is as dp[i] = dp[i – 1] + dp[i-2].
- Iterate over both the arrays:
- If(A[i] == B[j])
- count++, increase the lcs.
- Otherwise, increase i++, As the prefix of B should be matched.
- If(A[i] == B[j])
Below is the implementation of the code:
C++
#include <bits/stdc++.h> #include <iostream> using namespace std; // Maximum Length of longest Common // subsequence int solve( int N, int A[]) { // Create a array dp as B vector< int > dp(N + 1); dp[0] = 1; dp[1] = 1; for ( int i = 2; i <= N; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } int count = 0, j = 0; for ( int i = 0; i < N; i++) { // If elements are matched if (A[i] == dp[j]) { j++; count++; } if (j == dp.size()) { dp[i] = dp[i - 1] + dp[i - 2]; } } // Return the lcs length return count; } // Driver code int main() { int N = 6; int A[] = { 1, 2, 3, 1, 2, 3 }; // Function call cout << solve(N, A); return 0; } |
Java
import java.util.Arrays; public class Main { // Function to find the maximum length of the longest common subsequence static int solve( int N, int [] A) { // Create an array dp as B int [] dp = new int [N + 1 ]; dp[ 0 ] = 1 ; dp[ 1 ] = 1 ; for ( int i = 2 ; i <= N; i++) { dp[i] = dp[i - 1 ] + dp[i - 2 ]; } int count = 0 , j = 0 ; for ( int i = 0 ; i < N; i++) { // If elements are matched if (A[i] == dp[j]) { j++; count++; } if (j == dp.length) { dp[i] = dp[i - 1 ] + dp[i - 2 ]; } } // Return the LCS length return count; } // Driver code public static void main(String[] args) { int N = 6 ; int [] A = { 1 , 2 , 3 , 1 , 2 , 3 }; // Function call System.out.println(solve(N, A)); } } |
Python3
# Maximum Length of longest Common subsequence def solve(N, A): # Create an array dp as B dp = [ 0 ] * (N + 1 ) dp[ 0 ] = 1 dp[ 1 ] = 1 for i in range ( 2 , N + 1 ): dp[i] = dp[i - 1 ] + dp[i - 2 ] count = 0 j = 0 for i in range (N): # If elements are matched if A[i] = = dp[j]: j + = 1 count + = 1 if j = = len (dp): dp.append(dp[ - 1 ] + dp[ - 2 ]) # Return the LCS length return count # Driver code if __name__ = = "__main__" : N = 6 A = [ 1 , 2 , 3 , 1 , 2 , 3 ] # Function call print (solve(N, A)) |
C#
// C# code for the above approach using System; public class GFG { // Function to find the maximum length of the longest // common subsequence static int solve( int N, int [] A) { // Create an array dp as B int [] dp = new int [N + 1]; dp[0] = 1; dp[1] = 1; for ( int i = 2; i <= N; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } int count = 0, j = 0; for ( int i = 0; i < N; i++) { // If elements are matched if (A[i] == dp[j]) { j++; count++; } if (j == dp.Length) { dp[i] = dp[i - 1] + dp[i - 2]; } } // Return the LCS length return count; } // Driver code public static void Main() { int N = 6; int [] A = { 1, 2, 3, 1, 2, 3 }; // Function call Console.WriteLine(solve(N, A)); } } // This code is contributed by ragul21 |
Javascript
// Javascript code for the above approach // Maximum Length of longest Common // subsequence function solve(N, A) { // Create a array dp let dp = new Array(N + 1).fill(0); dp[0] = 1; dp[1] = 1; // finding the fibonacci series // by iteration method for (let i = 2; i <= N; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } let count = 0, j = 0; for (let i = 0; i < N; i++) { // If elements are matched if (A[i] == dp[j]) { j++; count++; } if (j == dp.length) { dp[i] = dp[i - 1] + dp[i - 2]; } } // Return the lcs length return count; } // Driver code let N = 6; let A = [1, 2, 3, 1, 2, 3]; // Function call console.log(solve(N, A)); // This code is contributed by ragul21 |
4
Time Complexity: O (N + M)
Auxiliary Space: O(N)
Contact Us