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。

自建示例

整个数组都满足递推关系:

输入:arr = [1,3,4,7,11,18]
输出:6
解释:1 + 3 = 4、3 + 4 = 7、4 + 7 = 11、7 + 11 = 18,因此整个数组就是长度 6 的合法子序列。

最短数组中不存在合法三元组:

输入:arr = [2,5,9]
输出:0
解释:数组长度为允许的最小值 3,但 2 + 5 不等于 9,且没有其他三项可选,因此不存在斐波那契式子序列。