本文共 1228 字，大约阅读时间需要 4 分钟。

题目地址：

给定一个严格升序数组$A$，求其中的最长的斐波那契数列的长度。数列的长度要求至少是$3$。

思路是动态规划。设$f[i][j]$是以$A[i],A[j]$结尾的最长斐波那契数列的长度。那么，如果$A$里有$A[j]-A[i]$，比如其下标是$x$，那么$f[i][j]=1+f[x][i]$，否则$f[i][j]=2$，这里还需要注意，$A[j]-A[i]<A[i]$要成立，也就是序列的次序不能变。代码如下：

import java.util.HashMap;import java.util.Map;public class Solution {       public int lenLongestFibSubseq(int[] A) {           Map
   
     map = new HashMap<>();        for (int i = 0; i < A.length; i++) {               map.put(A[i], i);        }                int res = 0;        int[][] dp = new int[A.length][A.length];        for (int i = 0; i < A.length; i++) {               for (int j = i + 1; j < A.length; j++) {                   dp[i][j] = 2;                int prev = A[j] - A[i];                                if (prev < A[i] && map.containsKey(prev)) {                       dp[i][j] = 1 + dp[map.get(prev)][i];                }                                res = Math.max(res, dp[i][j]);            }        }                return res > 2 ? res : 0;    }}
   

时空复杂度$O(n^2)$。

转载地址：http://gocs.baihongyu.com/