Finding the maximum-length contiguous subsequence in a given array that corresponds to a Fibonacci sequence is the problem of finding the longest prefix subsequence matching a Fibonacci sequence. A subsequence is a sequence that is created by taking out one or more elements from another sequence without altering the order of the elements that remain.

Example 1:

Input: N = 6, arr = {1, 2, 3, 1, 2, 3}

Output: 4

Explanation: Subsequence {1,1,2,3} of length 4.

Example 2:

Input: N = 5, arr = {2, 3, 1, 2, 5}

Output: 1

Explanation: Subsequence {1} of length 1

Approach: Using Dynamic Programming

The code uses dynamic programming to determine the length of the longest common subsequence between an input array and a sequence of Fibonacci numbers. It initializes an array, `fibonacciNumbers`, and iteratively fills it with Fibonacci numbers. If a match is found, the count is incremented, and the sequence is updated. The function returns the length of the longest common subsequence. The code demonstrates the usage of dynamic programming and prints the result.

Here’s the implementation of finding the longest prefix subsequence matching Fibonacci sequence using Dynamic Programming :

FileName:LongestCommonSubsequence.java

import java.util.Arrays;

public class LongestCommonSubsequence {

    // Function to find the maximum length of the longest common subsequence

    static int findLongestCommonSubsequence(int size, int[] array) {

        // Create an array dp as fibonacciNumbers

        int[] fibonacciNumbers = new int[size + 1];

        fibonacciNumbers[0] = 1;

        fibonacciNumbers[1] = 1;

        // Fill the fibonacciNumbers array

        for (int i = 2; i <= size; i++) {

            fibonacciNumbers[i] = fibonacciNumbers[i - 1] + fibonacciNumbers[i - 2];

        }

        int count = 0, j = 0;

        for (int i = 0; i < size; i++) {

            // If elements are matched

            if (array[i] == fibonacciNumbers[j]) {

                j++;

                count++;

            }

            // Check if the entire Fibonacci sequence is matched, and update if necessary

            if (j == fibonacciNumbers.length) {

                fibonacciNumbers[i] = fibonacciNumbers[i - 1] + fibonacciNumbers[i - 2];

            }

        }

        // Return the length of the longest common subsequence

        return count;

    }

    // Main method to demonstrate the function

    public static void main(String[] args) {

        int size = 6;

        int[] array = {1, 2, 3, 1, 2, 3};

        // Output the result of findLongestCommonSubsequence function

        System.out.println("Length of the Longest Common Subsequence: " + findLongestCommonSubsequence(size, array));

    }

}

Output:

Length of the Longest Common Subsequence: 4

Complexity analysis: The code has a time complexity of O(size) and a space complexity of O(size), where size is the input array's length. The loop filling the `fibonacciNumbers` array iterates from 2 to `size` once, requiring constant time operations. The main loop compares elements of the input array with Fibonacci numbers, running in linear time. The space complexity is linearly dependent on the size of the input array.

Using Iterative Approach

The `findLongestPrefixLength` method is an iterative approach to finding the length of the longest prefix subsequence in an array following the Fibonacci sequence. It initializes variables `maxLen` and `fib,` which represent the first two elements of the sequence. The method iterates through the input array `arr,` checking if each element matches the first element in the sequence. If a match is found, the algorithm increments `maxLen` the method returns the calculated `maxLen.`

Here’s the implementation of the iterative approach of finding the longest prefix subsequence matching Fibonacci sequence :

FileName:LongestPrefixSubsequence.java

public class LongestPrefixSubsequence {

    public static void main(String args[]) {

        int[] arr = {1, 2, 3, 1, 2, 3};

        int n = 6;

        System.out.println("Length of the Longest Common Subsequence: " + findLongestPrefixLength(n, arr));

    }

    static int findLongestPrefixLength(int N, int[] arr) {

        // Variable to store the length of the longest prefix subsequence

        int maxLen = 0;

        // Fibonacci sequence initialized with the first two elements

        int[] fib = {1, 1};

        // Loop through the array to find the longest prefix subsequence

        for (int i = 0; i < N; i++) {

            // Check if the current element matches the next element in the Fibonacci sequence

            if (arr[i] == fib[0]) {

                maxLen++;

                // Update the Fibonacci sequence for the next comparison

                int temp = fib[1];

                fib[1] = fib[0] + fib[1];

                fib[0] = temp;

            }

        }

        return maxLen;

    }

}

Output:

Length of the Longest Common Subsequence: 4

Complexity analysis: Because each element of the input array 'arr' is processed once, the iterative approach has an O(N) time complexity. Since the variables "maxLen," "fib," and "temp" require a constant amount of space, the space complexity is O(1). The algorithm has linear time complexity after iterating through the array once to verify and update the elements of the Fibonacci sequence. Since the space complexity is independent of the input size, it stays constant.

← Prev Next →

Longest Prefix Subsequence matching Fibonacci Sequence in Java

Approach: Using Dynamic Programming

Using Iterative Approach