905. Length Of Longest Fibonacci Subsequence¶

Difficulty: Medium

905. Length of Longest Fibonacci Subsequence

Medium

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 arr by deleting any number of elements (including none) from arr, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].

Example 1:

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

Example 2:

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

Constraints:

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

Solution¶

class Solution {
    private HashMap<Integer, TreeSet<Integer>> map;
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        int maxi = 0;
        map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (map.containsKey(arr[i])) {
                TreeSet<Integer> temp = new TreeSet<>();
                temp = map.get(arr[i]);
                temp.add(i);
                map.put(arr[i] , new TreeSet<>(temp));
            }
            else {
                map.put(arr[i] , new TreeSet<Integer>());
                TreeSet<Integer> temp = new TreeSet<>();
                temp.add(i);
                map.put(arr[i] , new TreeSet<>(temp)); 
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int a = arr[i] , b = arr[j];
                int count = 2, prev_ind = j;
                while (true) {
                    //check find the first index greater than prev_ind which is equal to a + b;
                    int res = check(a + b , prev_ind, n - 1);
                    if (res == -1) break;
                    else {
                        prev_ind = res;
                        int search = a + b;
                        a = b;
                        b = search;
                        count++;
                    }
                }
                if (count >= 3) maxi = Math.max(maxi, count);
            }
        }
        return maxi;
    }
    private int check(int target, int low, int high) {
        if (map.containsKey(target)) {
            TreeSet<Integer> current = map.get(target);
            if (current.higher(low) != null) return current.higher(low);
            return -1;
        }
        return -1;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here