0 dynamic programming medium leetcode873. Length of the longest Fibonacci subsequence

873. The length of the longest Fibonacci subsequence

describe

If the sequence X_1, X_2, …, X_n Meet the following conditions , Just say it's Fibonacci Of ：

n >= 3
For all i + 2 <= n, There are X_i + X_{i+1} = X_{i+2}
Given a strictly increasing array of positive integers to form a sequence arr , find arr The length of the longest fibonaccian subsequence in . If one doesn't exist , return 0 .

（ Think about it , Subsequences are derived from the original sequence arr Derived from , It is from arr Delete any number of elements in the （ It's also possible to delete ）, Without changing the order of the rest of the elements . for example , [3, 5, 8] yes [3, 4, 5, 6, 7, 8] A subsequence of ）

 Example  1：

 Input : arr = [1,2,3,4,5,6,7,8]
 Output : 5
 explain :  The longest Fibonacci subsequence is  [1,2,3,5,8] .
 Example  2：

 Input : arr = [1,3,7,11,12,14,18]
 Output : 3
 explain :  The longest Fibonacci subsequence is  [1,11,12]、[3,11,14]  as well as  [7,11,18] .
 

 Tips ：

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

 source ： Power button （LeetCode）
 link ：https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

There are three values to consider , Before fixation ( Or after ) Two keep testing the third .
Double loop considers all combinations of two numbers , Then judge whether there is a third one that meets the conditions in the following numbers , If there is , Update length

class Solution {
    
    public int lenLongestFibSubseq(int[] arr) {
    
        int n = arr.length;
        int[][] dp = new int[n][n];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
    
            map.put(arr[i],i);
        }
        int ans = 0;
        for (int i = 0; i <n; i++) {
    
            for (int j = i + 1; j < n; j++) {
    
                int c = arr[i]+arr[j];
                if (map.containsKey(c)) {
    
                    dp[j][map.get(c)] = dp[i][j] == 0 ? 3 : dp[i][j] + 1;
                    ans = Math.max(ans,dp[j][map.get(c)]);
                }
            }
        }
        return ans;
    }
}