BAT面试算法进阶(10)- 最长的斐波那契子序列的长度(暴力法)

面试题目

如果序列X_1,X_2,...,X_n 满足下列条件,就说它是 斐波拉契式的:

• n >= 3
• 对于所有 i+2 <= n ,都有X_i + X_{i+1} = X_{i+2} ;

给定一个严格递增的正整数数组形成序列.找到A中最长的斐波拉契式子序列的长度.如果一个不存在,返回0.比如,子序列是从原序列A中派生出来的.它从A中删除任意数量的元素.而不改变其元素的顺序.例如[3,5,8]是[3,4,5,6,7,8]的子序列.

案例

案例(1)

• 输入:[1,2,3,4,5,6,7,8]
• 输出: 5
• 原因: 最长的斐波拉契式子序列: [1,2,3,5,8]

案例(2)

• 输入:[1,3,7,11,12,14,18]
• 输出: 3
• 原因: 最长的斐波拉契式子序列: [1,11,12],[3,11,14],[7,11,18]

解决方案-- 使用Set(集合)暴力法

• 思路

每个斐波拉契的子序列都依靠2个相邻项来确定下一个预期项,例如,对于2,5.我们所期望的子序列必定以7,12,19,31等继续.

我们可以使用set结构来快速确定下一项是否在数组A中.由于这些项的值以指数形式增长.最大值<= 10^9的斐波拉契式的子序列有43项目.

• 算法

对于每个起始对A[i],A[j].我们保持下一个预期值. y = A[i] + ``A[j].和此前看到的最大值x = A[j].如果Y在数组中,我们可以更新这些值 (x,y) -> (y,x+y).

注意: 由于子序列的长度大于等于3,只能是斐波拉契式的,所以我们必须进行检查ans >= 3?ans:0

代码实现

• C++ Code

• Java Code

• python Code

复杂度分析

• 时间复杂度: O(N^2logM),其中N指的是A的长度,M指的是A的最大值
• 空间复杂度: O(N) ,集合S的使用空间

学习建议

• 理解斐波拉契式数列的规律
• 理解代码思路