Length of Longest Fibonacci Subsequence | Leetcode 873

/*
//Approach-1: Greedy Simulation...TC: O(N^2 logM)...SC: O(N)
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n=arr.size();
        unordered_set<int> values(arr.begin(),arr.end());
        
        int longest=0;
        for(int i=0;i<n-1;++i){
            for(int j=i+1;j<n;++j){
                int a = arr[i];
                int b = arr[j];
                int fib_len = 2;
                while(values.count(a+b)>0){
                    int sum = a+b;
                    a = b;
                    b = sum;
                    fib_len++;
                }
                if(fib_len>2)
                    longest = max(longest,fib_len);
            }
        }
        return longest;
    }
};

//Approach-2: Binary Search...TC: O(N^2 logN)...SC: O(1)
class Solution {
    int fibChainLength(vector<int>& arr,int a,int b,int& n){
        int fib_idx = lower_bound(arr.begin(),arr.end(),a+b)-arr.begin();
        if(fib_idx<n and arr[fib_idx]==a+b)
            return 1 + fibChainLength(arr,b,a+b,n);
        return 0;
    }
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n=arr.size();
        int longest=0;
        for(int i=0;i<n-1;++i){
            for(int j=i+1;j<n;++j){
                int a=arr[i];
                int b=arr[j];
                int fib_len = fibChainLength(arr,a,b,n);
                if(fib_len>0)
                    longest = max(longest,2+fib_len);
            }
        }
        return longest;
    }
};
*/
//Approach-3: Dynamic Programming...TC:O(N^2)...SC:O(N^2)
class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n=arr.size();
        vector<vector<int>> dp(n,vector<int>(n));
        //(Subproblem) dp[x][y]: Longest fib chain length ending at 'y' with 'x' being the previous item

        int longest=0;
        for(int sum=2;sum<n;++sum){
            int a=0;
            int b=sum-1;
            //Two-Sum approach
            while(a<b){
                if(arr[a]+arr[b]<arr[sum])       a++;
                else if(arr[a]+arr[b]>arr[sum])  b--;
                else{
                    dp[b][sum] = 1+dp[a][b];
                    longest = max(longest,dp[b][sum]);
                    a++;
                    b--;
                }
            }
        }
        return longest==0? 0 : 2+longest;
    }
};
/*
//JAVA
import java.util.*;

class Solution {
    // Approach-1: Greedy Simulation
    public int lenLongestFibSubseqGreedy(int[] arr) {
        int n = arr.length;
        Set<Integer> values = new HashSet<>();
        for (int num : arr) values.add(num);

        int longest = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int a = arr[i];
                int b = arr[j];
                int fibLen = 2;
                while (values.contains(a + b)) {
                    int sum = a + b;
                    a = b;
                    b = sum;
                    fibLen++;
                }
                if (fibLen > 2) longest = Math.max(longest, fibLen);
            }
        }
        return longest;
    }

    // Approach-2: Binary Search
    private int fibChainLength(int[] arr, int a, int b, int n) {
        int fibIdx = Arrays.binarySearch(arr, a + b);
        if (fibIdx >= 0 && fibIdx < n) {
            return 1 + fibChainLength(arr, b, a + b, n);
        }
        return 0;
    }

    public int lenLongestFibSubseqBinarySearch(int[] arr) {
        int n = arr.length;
        int longest = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int a = arr[i];
                int b = arr[j];
                int fibLen = fibChainLength(arr, a, b, n);
                if (fibLen > 0) longest = Math.max(longest, 2 + fibLen);
            }
        }
        return longest;
    }

    // Approach-3: Dynamic Programming
    public int lenLongestFibSubseqDP(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        int longest = 0;

        for (int sum = 2; sum < n; sum++) {
            int a = 0;
            int b = sum - 1;
            while (a < b) {
                if (arr[a] + arr[b] < arr[sum]) {
                    a++;
                } else if (arr[a] + arr[b] > arr[sum]) {
                    b--;
                } else {
                    dp[b][sum] = 1 + dp[a][b];
                    longest = Math.max(longest, dp[b][sum]);
                    a++;
                    b--;
                }
            }
        }
        return longest == 0 ? 0 : 2 + longest;
    }
}

#Python
from bisect import bisect_left

class Solution:
    # Approach-1: Greedy Simulation
    def lenLongestFibSubseqGreedy(self, arr):
        n = len(arr)
        values = set(arr)
        longest = 0

        for i in range(n - 1):
            for j in range(i + 1, n):
                a, b = arr[i], arr[j]
                fib_len = 2
                while a + b in values:
                    a, b = b, a + b
                    fib_len += 1
                if fib_len > 2:
                    longest = max(longest, fib_len)
        return longest

    # Approach-2: Binary Search
    def fibChainLength(self, arr, a, b, n):
        idx = bisect_left(arr, a + b)
        if idx < n and arr[idx] == a + b:
            return 1 + self.fibChainLength(arr, b, a + b, n)
        return 0

    def lenLongestFibSubseqBinarySearch(self, arr):
        n = len(arr)
        longest = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                a, b = arr[i], arr[j]
                fib_len = self.fibChainLength(arr, a, b, n)
                if fib_len > 0:
                    longest = max(longest, 2 + fib_len)
        return longest

    # Approach-3: Dynamic Programming
    def lenLongestFibSubseqDP(self, arr):
        n = len(arr)
        dp = [[0] * n for _ in range(n)]
        longest = 0

        for sum_idx in range(2, n):
            a, b = 0, sum_idx - 1
            while a < b:
                if arr[a] + arr[b] < arr[sum_idx]:
                    a += 1
                elif arr[a] + arr[b] > arr[sum_idx]:
                    b -= 1
                else:
                    dp[b][sum_idx] = 1 + dp[a][b]
                    longest = max(longest, dp[b][sum_idx])
                    a += 1
                    b -= 1
        return 2 + longest if longest > 0 else 0

*/