Track the Maximum Length:

For each valid pair (j, i), update a variable max_len with the maximum value of dp[j][i].

Iteration:

Use two nested loops:
- Outer loop with i (current endpoint of the sequence).
- Inner loop with j (second-to-last number).
For each pair, compute the third-to-last number and update the DP table using the recurrence relation.

Final Output:

Return max_len if it is greater than or equal to 3. Otherwise, return 0 (indicating no valid Fibonacci-like subsequence exists).

Code

[{"language":"Java","code":"class Solution {\n    public int lenLongestFibSubseq(int[] arr) {\n        int n = arr.length;\n        int[][] dp = new int[n][n]; // To store the Fibonacci-like subsequence lengths\n        Map<Integer, Integer> indexMap = new HashMap<>(); // To map values to their indices\n        int maxLen = 0; // To track the maximum length\n\n        // Populate the map with elements and their indices\n        for (int i = 0; i < n; i++) {\n            indexMap.put(arr[i], i);\n        }\n\n        // Iterate backward through the array\n        for (int i = n - 1; i >= 0; i--) {\n            for (int j = n - 1; j > i; j--) {\n                int first = arr[i];\n                int second = arr[j];\n                int currLen = 2; // Start the subsequence with length 2\n\t\t\t\t\n\t\t\t\tint third = first + second; // Calculate the next number in the sequence\n                \n                if (indexMap.containsKey(third)) { // Check if `third` exists in the map\n                    int k = indexMap.get(third); // Retrieve the index of `third`\n                    // Extend the Fibonacci-like subsequence\n                    currLen = dp[j][k] + 1;\n                    maxLen = Math.max(maxLen, currLen); // Update the maximum

Related Tags