[leetcode] 873. Length of Longest Fibonacci Subsequence

[leetcode] 873. Length of Longest Fibonacci Subsequence

Description

A sequence X_1, X_2, …, X_n is fibonacci-like if:

n >= 3X_i + X_{i+1} = X_{i+2} for all i + 2 <= n

Given a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A. If one does not exist, return 0.

(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].)

Example 1:

Input: [1,2,3,4,5,6,7,8]Output: 5Explanation:The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: [1,3,7,11,12,14,18]Output: 3Explanation:The longest subsequence that is fibonacci-like:[1,11,12], [3,11,14] or [7,11,18].

Note:

3 <= A.length <= 10001 <= A[0] < A[1] < … < A[A.length - 1] <= 10^9(The time limit has been reduced by 50% for submissions in Java, C, and C++.)

分析

题目的意思是：题目的意思是给你一个数组，找出最长的fibonacci数列，我开始用到暴力求解的方法，写了两个大循环，后面看答案还有动态规划的解法，我这里欣赏一下，顺便分享出来，方便大家一同进步。大致思路是首先建立一个关于A的值和索引的字典，然后按照求最长递增子序列的方法遍历，如果(i,j)，(j,k)相连，则

longest[j, k] = longest[i, j] + 1

细节我也不是很懂，经常看应该就懂了

代码

class Solution: def lenLongestFibSubseq(self, A: List[int]) -> int: index_dict={} for index,item in enumerate(A): index_dict[item]=index longest=collections.defaultdict(lambda:2) res=0 for index,value in enumerate(A): for j in range(index): i=index_dict.get(value-A[j],None) if(i is not None and i

参考文献

​​[LeetCode] Approach 2: Dynamic Programming​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。