Length of Longest Fibonacci Subsequence

Leetcode Problem:

• Length of Longest Fibonacci Subsequence

Summary

• The problem is to find the length of the longest Fibonacci-like subsequence in a given strictly increasing array of positive integers.

Approach

• The solution uses a binary search approach to find the longest Fibonacci-like subsequence
• It first sorts the array and then uses a binary search to find the length of the longest Fibonacci-like subsequence.

Complexity

• O(n log n) due to the binary search and O(n^2) due to the nested loops in the combi function.

Explanation

• The solution starts by sorting the array
• Then it uses a binary search to find the length of the longest Fibonacci-like subsequence
• The binary search is performed by checking if a number exists in the array
• If it does, the function returns true, otherwise it returns false
• The function then uses a combi function to find the longest Fibonacci-like subsequence
• The combi function uses a depth-first search approach to find the longest Fibonacci-like subsequence
• It starts by adding the first two elements of the array to the selected vector and then recursively calls itself with the remaining elements of the array
• The function then checks if the length of the selected vector is greater than 2 and if the length of the selected vector plus 1 is equal to the next element in the array
• If it is, the function increments the depth and the ans variable
• The function then pops the last element from the selected vector and recursively calls itself with the remaining elements of the array
• The function continues this process until the depth is greater than 2 or the end of the array is reached
• The function then returns the ans variable, which represents the length of the longest Fibonacci-like subsequence.

Solution Code:

class Solution {
public:
    int ans = 0;
    bool checkNum(int n, vector& arr){
        int l = 0;
        int r = arr.size() - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(arr[mid] == n) return true;
            if(arr[mid] < n){
                l = mid + 1;
            } else{
                r = mid - 1;
            }
        }
        return false;
    }

    void combi(vector&arr, int cur, int depth, vector& selected){
        if(depth == 2){
            int a =  selected[0];
            int b =  selected[1];
            int cnt = 0;
            while(checkNum(a + b, arr)){
                int t = a + b;
                a = b;
                b = t;
                cnt++;
            }
            if(cnt >= 1){
                ans = max(ans, depth + cnt);
            }
            return;
        }

        for(int i = cur + 1; i < arr.size(); i++){
            selected.push_back(arr[i]);
            combi(arr, i, depth + 1, selected);
            selected.pop_back();
        }
    }
    int lenLongestFibSubseq(vector& arr) {
        vector selected;
        combi(arr, -1, 0, selected);
        return ans;
    }
};