873. Length of Longest Fibonacci Subsequence

Problem Description

A sequence x₁, x₂, ..., x_n is Fibonacci-like if:

• n ≥ 3
• x_i + x_i+1 = x_i+2 for all i + 2 ≤ n

Given a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of arr. If one does not exist, return 0.

A subsequence is derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Examples:

Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: The longest Fibonacci-like subsequence is [1,2,3,5,8].

Input: arr = [1,3,7,11,12,14,18]
Output: 3
Explanation: The longest Fibonacci-like subsequence is [1,11,12], [3,11,14] or [7,11,18].

Constraints:

• 3 ≤ arr.length ≤ 1000
• 1 ≤ arr[i] < arr[i + 1] ≤ 10⁹

Python Solution

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        s = set(arr)
        n = len(arr)
        max_len = 0
        
        # Try all possible pairs as first two numbers
        for i in range(n):
            for j in range(i + 1, n):
                # Current first two numbers
                x, y = arr[i], arr[j]
                length = 2
                
                # Keep finding next Fibonacci number
                while x + y in s:
                    x, y = y, x + y
                    length += 1
                
                max_len = max(max_len, length)
        
        return max_len if max_len >= 3 else 0

Implementation Notes:

• Uses set for O(1) lookup of next Fibonacci number
• Time complexity: O(n² * log M) where M is the maximum value in arr
• Space complexity: O(n)

Java Solution

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        Set set = new HashSet<>();
        for (int num : arr) {
            set.add(num);
        }
        
        int maxLen = 0;
        
        // Try all possible pairs as first two numbers
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Current first two numbers
                int x = arr[i], y = arr[j];
                int length = 2;
                
                // Keep finding next Fibonacci number
                while (set.contains(x + y)) {
                    int temp = y;
                    y = x + y;
                    x = temp;
                    length++;
                }
                
                maxLen = Math.max(maxLen, length);
            }
        }
        
        return maxLen >= 3 ? maxLen : 0;
    }
}

C++ Solution

class Solution {
public:
    int lenLongestFibSubseq(vector& arr) {
        int n = arr.size();
        unordered_set s(arr.begin(), arr.end());
        int maxLen = 0;
        
        // Try all possible pairs as first two numbers
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Current first two numbers
                int x = arr[i], y = arr[j];
                int length = 2;
                
                // Keep finding next Fibonacci number
                while (s.count(x + y)) {
                    int temp = y;
                    y = x + y;
                    x = temp;
                    length++;
                }
                
                maxLen = max(maxLen, length);
            }
        }
        
        return maxLen >= 3 ? maxLen : 0;
    }
};

JavaScript Solution

/**
 * @param {number[]} arr
 * @return {number}
 */
var lenLongestFibSubseq = function(arr) {
    const s = new Set(arr);
    const n = arr.length;
    let maxLen = 0;
    
    // Try all possible pairs as first two numbers
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            // Current first two numbers
            let x = arr[i], y = arr[j];
            let length = 2;
            
            // Keep finding next Fibonacci number
            while (s.has(x + y)) {
                const temp = y;
                y = x + y;
                x = temp;
                length++;
            }
            
            maxLen = Math.max(maxLen, length);
        }
    }
    
    return maxLen >= 3 ? maxLen : 0;
};

C# Solution

public class Solution {
    public int LenLongestFibSubseq(int[] arr) {
        int n = arr.Length;
        var set = new HashSet(arr);
        int maxLen = 0;
        
        // Try all possible pairs as first two numbers
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Current first two numbers
                int x = arr[i], y = arr[j];
                int length = 2;
                
                // Keep finding next Fibonacci number
                while (set.Contains(x + y)) {
                    int temp = y;
                    y = x + y;
                    x = temp;
                    length++;
                }
                
                maxLen = Math.Max(maxLen, length);
            }
        }
        
        return maxLen >= 3 ? maxLen : 0;
    }
}

Implementation Notes:

• Uses HashSet for O(1) lookup of next Fibonacci number
• Time complexity: O(n² * log M)
• Space complexity: O(n)