【DP】873. Length of Longest Fibonacci Subsequence

题目描述：

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

• n >= 3
• X_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: 5
Explanation:
The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

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

解题思路：

这道题是求最长斐波那契子序列，做法：

• 两层 for 循环，得到斐波那契的前两个数 first 和 second；
• 判断这两个数的和（第三个数）third 是否在数组中；
• 如果 third 在数组中，斐波那契三个数整体前进一步，即更新这三个数： first = second, second = third, third = first + second，长度加 1，然后回到上一步继续判断；
• 如果 third 不在数组中，更新最大长度的值。

注意：在编程的时候，数组转化为集合 set，可以使判断 third 的时间复杂度为 O(1)。

时间复杂度为 O((N^2) * logM)，log M 来自于循环判断 third 是否在数组中；空间复杂度为 O(N)，即开辟集合 set 所占大小。

Python3 实现：

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        setA = set(A)
        ans = 0
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                first, second = A[i], A[j]
                third = first + second
                length = 2
                while third in setA:  # 当 third 在数组中，更新三个值继续判断
                    length += 1
                    first = second
                    second = third
                    third = first + second
                ans = max(ans, length)  # 更新最大长度
        return ans if ans >= 3 else 0