面试算法93:最长斐波那契数列

发布时间:2024年01月05日

题目

输入一个没有重复数字的单调递增的数组,数组中至少有3个数字,请问数组中最长的斐波那契数列的长度是多少?例如,如果输入的数组是[1,2,3,4,5,6,7,8],由于其中最长的斐波那契数列是1、2、3、5、8,因此输出是5。

分析

由于状态转移方程有两个参数i和j,因此需要一个二维数组来缓存f(i,j)的计算结果。i对应二维数组的行号,j对应二维数组的列号。由于i大于j,因此实际上只用到了二维数组的左下角部分。如果数组的长度是n,那么i的取值范围为1~n-1,而j的取值范围为0~n-2。
在这里插入图片描述
表14.4中第2行第1个格子表示以A[2]为结尾、A[0]为倒数第2个数字的数列1、3,此时还不是一个有效的斐波那契数列,它的长度是2,即f(2,0)等于2。第2行第2个格子表示以A[2]为结尾、A[1]为倒数第2个数字的斐波那契数列的长度。存在一个数字A[0]使A[2]=A[1]+A[0](即3=2+1),因此f(2,1)=f(1,0)+1,f(2,1)等于3,对应的斐波那契数列是1、2、3。

public class Test {
    public static void main(String[] args) {
        int[] A = {1, 2, 3, 4, 5, 6, 7, 8};
        int result = lenLongestFibSubseq(A);
        System.out.println(result);

    }

    public static int lenLongestFibSubseq(int[] A) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            map.put(A[i], i);
        }

        int[][] dp = new int[A.length][A.length];
        int result = 2;
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                int k = map.getOrDefault(A[i] - A[j], -1);
                dp[i][j] = k >= 0 && k < j ? dp[j][k] + 1 : 2;

                result = Math.max(result, dp[i][j]);
            }
        }

        return result > 2 ? result : 0;
    }

}
文章来源:https://blog.csdn.net/GoGleTech/article/details/135406419
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。