用你我的双手,传递技术! 把碎片时间用起来,每天进步一点点!
如果序列X_1,X_2,...,X_n
满足下列条件,就说它是 斐波拉契式的:
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,2,3,4,5,6,7,8]
[1,2,3,5,8]
[1,3,7,11,12,14,18]
[1,11,12],[3,11,14],[7,11,18]
将斐波拉契式的子序列中的2个连续项A[i],A[j] 视为单个结点(i,j).整个子序列是这些连续结点的之间的路径.例如,对于斐波拉契式的子序列,(A[1] = 2,A[2] = 3,A[4] = 5,A[7] = 8,A[10] = 13)
,结点的路径就为(1,2)<->(2,3)<->(4,7)<->(7,10).
这样做的目的,只有当A[i]+A[j] == A[k]
时.两结点(i,j)和(j,k)
才是连贯的.我们需要这个信息才能知道它们之间是可以连通的.
设longest[i,j]
是结束在[i,j]
的最长路径.那么如果(i,j)
和(j,k)
是连通的,longest[j,k] = longest[i,j]+1
.由于 i
是由A.index(A[k] - A[j])
唯一确定的.我们在 i
检查每组j < k
,并相应更新longest[j,k]
O(N^2)
,其中N指的是A的长度O(NlogM)
,其中M是A中的最大的元素.胖C,很愿意做这样的分享! 技术分享是很值的一直做的事.也希望大家能够动动手转发.分享给更多人!
本文分享自 HelloCode开发者学习平台 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!