Untitled

import java.util.*;

public class LongestFibSubseq {

    public static int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexMap.put(arr[i], i);
        }

        int maxLength = 0;

        // Memoization map to store results of recursive calls
        Map<String, Integer> memo = new HashMap<>();

        // Start exploring pairs (i, j) where i < j
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                maxLength = Math.max(maxLength, 2 + findFibLength(arr, i, j, indexMap, memo));
            }
        }

        return maxLength >= 3 ? maxLength : 0;
    }

    private static int findFibLength(int[] arr, int i, int j, Map<Integer, Integer> indexMap, Map<String, Integer> memo) {
        // Create a unique key for memoization
        String key = i + "," + j;

        // If the result for this pair is already calculated, return it
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // Calculate the next value in the Fibonacci sequence
        int nextValue = arr[i] + arr[j];

        // Check if the next value exists in the array
        if (indexMap.containsKey(nextValue)) {
            int k = indexMap.get(nextValue);
            // Recursively find the length including this next value
            int length = 1 + findFibLength(arr, j, k, indexMap, memo);
            memo.put(key, length);
            return length;
        }

        // Base case: no further Fibonacci sequence can be formed
        return 0;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5, 6, 7, 8};
        int[] arr2 = {1, 3, 7, 11, 12, 14, 18};

        System.out.println(lenLongestFibSubseq(arr1)); // Output: 5
        System.out.println(lenLongestFibSubseq(arr2)); // Output: 3
    }
}