0873. Length of Longest Fibonacci Subsequence¶
题目信息¶
- 题号:
0873
- 难度:
Medium
- 主题:
严格递增数组、子序列、斐波那契关系
- 原题:
- 重点:
选择保持原下标顺序的子序列,长度至少为 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,且没有其他三项可选,因此不存在斐波那契式子序列。