0873. Length of Longest Fibonacci Subsequence ======================================================================================================================== 题目信息 -------- :题号: 0873 :难度: Medium :主题: 严格递增数组、子序列、斐波那契关系 :原题: `LeetCode 0873 `_ :重点: 选择保持原下标顺序的子序列,长度至少为 3;从第三项起每项等于前两项之和,不存在时返回 0 题目重述 -------- 给定一个严格递增的正整数数组 ``arr``。从中删除任意数量的元素但保持剩余元素原有顺序,可以得到一个子序列。 若子序列长度至少为 ``3``,并且从第三项开始每个元素都等于前两个元素之和,则它是斐波那契式子序列。请返回最长此类子序列的长度;若不存在长度至少为 ``3`` 的合法子序列,返回 ``0``。 ``3 <= arr.length <= 1000``,``1 <= arr[i] < arr[i + 1] <= 10^9``。 自建示例 -------- 整个数组都满足递推关系: .. code-block:: text 输入:arr = [1,3,4,7,11,18] 输出:6 解释:1 + 3 = 4、3 + 4 = 7、4 + 7 = 11、7 + 11 = 18,因此整个数组就是长度 6 的合法子序列。 最短数组中不存在合法三元组: .. code-block:: text 输入:arr = [2,5,9] 输出:0 解释:数组长度为允许的最小值 3,但 2 + 5 不等于 9,且没有其他三项可选,因此不存在斐波那契式子序列。