Horje
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.

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

Output

4

Time Complexity: O (N + M)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Minimum Operations to Reduce X to Zero Minimum Operations to Reduce X to Zero
Minimum sum of Quotients after performing the given operation Minimum sum of Quotients after performing the given operation
Find Next Optimal Range in Array Find Next Optimal Range in Array
Minimum Jumps with Specific NUM Value Minimum Jumps with Specific NUM Value
Minimum Subarray sum with atleast one repeated value. Minimum Subarray sum with atleast one repeated value.

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje