Length Of Longest Fibonacci Subsequence - Leetcode Solution

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.

1