Solution For Length Of Longest Fibonacci Subsequence

Problem Description:
Given a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A. If one does not exist, return 0.

A sequence X1, X2, …, Xn is fibonacci-like if:

n >= 3
Xi + Xi+1 = Xi+2 for all i + 2 <= n

Solution:
We can use dynamic programming to solve this problem. First, let’s consider a naive solution where we iterate through each pair of numbers and find the fibonacci sequence starting from those numbers. This would take O(n^2 * log(max(A))) time, which is not efficient enough for large inputs.

To optimize this solution, we can use dynamic programming to store the fibonacci sequence starting from each number, and then use these sequences to find longer fibonacci-like subsequence. Let dp[i][j] be the length of the longest fibonacci-like subsequence ending at A[i] and A[j]. Since A is strictly increasing, we know that A[i] < A[j]. Then, we can calculate dp[i][j] as follows:

If A[k] = A[i] + A[j] for some k > j, then dp[j][k] = dp[i][j] + 1, since we can extend the fibonacci-like subsequence ending at A[i] and A[j] with A[k].
Otherwise, dp[i][j] = 2, since A[i] and A[j] can be the first two numbers of a fibonacci-like subsequence.

We can compute dp[i][j] for all i < j in O(n^2) time. Then, the answer is simply the maximum value in the dp array.

Python Code:

def lenLongestFibSubseq(A: List[int]) -> int:
n = len(A)
dp = [[2] * n for _ in range(n)] indices = {num: i for i, num in enumerate(A)}

ans = 0
for j in range(1, n):
    for i in range(j):
        k = indices.get(A[j] - A[i], -1)
        if k >= 0 and k < i:
            dp[i][j] = dp[k][i] + 1
            ans = max(ans, dp[i][j])

return ans if ans > 2 else 0

Time Complexity:
The time complexity of this solution is O(n^2), where n is the length of the input array. This is because we iterate through each pair of numbers in the input array, and for each pair we check whether there is a number in the input array that can extend the fibonacci-like subsequence.

Space Complexity:
The space complexity of this solution is also O(n^2), since we need to store a two-dimensional array of size n x n for the dp table.

Step by Step Implementation For Length Of Longest Fibonacci Subsequence

public int lenLongestFibSubseq(int[] A) {
        int N = A.length;
        Set S = new HashSet();
        for (int x: A)
            S.add(x);

        int ans = 0;
        for (int i = 0; i < N; ++i)
            for (int j = i+1; j < N; ++j) {
                /* With x = A[i], y = A[j], find the length
                 * of the longest fibonacci-like subsequence
                 * ending with x and y. */
                int x = A[i], y = A[j];
                int length = 2;
                while (S.contains(x+y)) {
                    int tmp = y;
                    y = x + y;
                    x = tmp;
                    ans = Math.max(ans, ++length);
                }
            }

        return ans >= 3 ? ans : 0;
    }

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        #Create a set for fast lookup
        s = set(A)
        #initialize max length to 0
        max_len = 0
        #Loop through the array
        for i in range(len(A)):
            #Loop through the array again starting at the next element
            for j in range(i+1, len(A)):
                #initialize length to 2 (since we have 2 elements already)
                length = 2
                #first and second are the two elements we are currently looking at
                first, second = A[i], A[j]
                #while the sum of the two elements is in the set
                while first+second in s:
                    #increment the length
                    length += 1
                    #update first and second to be the next two elements in the sequence
                    first, second = second, first+second
                #update max_len if necessary
                max_len = max(max_len, length)
        #return max_len
        return max_len

/**
 * @param {number[]} A
 * @return {number}
 */
var lenLongestFibSubseq = function(A) {
    // create a set for fast lookups
    const set = new Set(A);
    // result will keep track of the longest length found so far
    let result = 0;
    
    // we iterate through each possible starting pair
    for (let i = 0; i < A.length; i++) {
        for (let j = i + 1; j < A.length; j++) {
            // current length of the subsequence
            let length = 2;
            // first and second are the starting numbers of the subsequence
            let first = A[i];
            let second = A[j];
            // next is the next number in the subsequence
            let next = first + second;
            
            // while the next number in the subsequence exists in the set
            while (set.has(next)) {
                // update the current length
                length++;
                // update first and second to be the second and next numbers
                first = second;
                second = next;
                // update next to be the sum of the new first and second
                next = first + second;
            }
            
            // if the current length is longer than the longest length found so far, update the result
            if (length > result) {
                result = length;
            }
        }
    }
    
    // if no subsequence was found, return 0
    if (result === 2) {
        return 0;
    }
    
    // return the longest length found
    return result;
};

int lenLongestFibSubseq(vector& A) 
{
    int N = A.size();
    unordered_set S(A.begin(), A.end());
    int ans = 0;

    for (int i = 0; i < N; ++i)
        for (int j = i+1; j < N; ++j) {
            /* With the starting pair (A[i], A[j]),
             * y represents the future expected value in
             * the sequence, and x represents the most current
             * value found. */
            int x = A[j], y = A[i] + A[j];
            int length = 2;

            while (S.find(y) != S.end()) {
                int temp = y;
                y += x;
                x = temp;
                ans = max(ans, ++length);
            }
        }

    return ans >= 3 ? ans : 0;
}

public int LenLongestFibSubseq(int[] A) { // Create a map to store the values in the array // and their corresponding indices HashMap map = new HashMap<>(); for(int i = 0; i < A.length; i++) { map.put(A[i], i); } int max = 0; // Outer loop: iterate over all possible starting points for a Fibonacci sequence for(int i = 0; i < A.length - 1; i++) { // Inner loop: iterate over all possible ending points for a Fibonacci sequence // that starts at the current index for(int j = i + 1; j < A.length; j++) { // Find the length of the longest Fibonacci sequence that starts // at index i and ends at index j int curr = A[j]; int prev = A[i]; int len = 2; // While we can find the next value in the Fibonacci sequence, // keep looking while(map.containsKey(prev + curr)) { // Update the current and previous values, and increment the length int temp = curr; curr = prev + curr; prev = temp; len++; } // Update the maximum length if necessary max = Math.max(max, len); } } // If no Fibonacci sequence was found, return 0 if(max == 2) { return 0; } // Otherwise, return the maximum length return max; }