873. Length of Longest Fibonacci Subsequence

Link

Solution

dp[i][j] denotes the max length fib seq which start by A[i] and end with A[j]

dp[i][j] = dp[k][i] + 1; if we can find A[k] == A[j] - A[i] where k < i

 public int lenLongestFibSubseq(int[] A) {
        int N = A.length;
        int[][] dp = new int[N][N];
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int j = 0; j < N; j++){
            map.put(A[j], j);
            for(int i = 0; i < j; i++){
                int k = map.getOrDefault(A[j]-A[i], -1);
                dp[i][j] = k >= 0 && k < i ? dp[k][i] + 1 : 2;
                res = Math.max(res, dp[i][j]);
            }
        }
        return res > 2 ? res : 0;
        
    }