class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
}
};
剑指 Offer II 093. 最长斐波那契数列
如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：
n >= 3i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
示例 1：
输入: arr = [1,2,3,4,5,6,7,8] 输出: 5 解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
示例 2：
输入: arr = [1,3,7,11,12,14,18] 输出: 3 解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。
提示：
3 <= arr.length <= 10001 <= arr[i] < arr[i + 1] <= 10^9
注意：本题与主站 873 题相同： https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/
原站题解
python3 解法, 执行用时: 2056 ms, 内存消耗: 22.8 MB, 提交时间: 2022-11-22 15:46:55
'''
定义二维数组 dp 表示以每个下标对的元素作为最后两个数字的斐波那契子序列的最大长度。
当 i>j 时，dp[j][i] 表示以 arr[j] 和 arr[i] 作为最后两个数字的斐波那契子序列的最大长度。初始时 dp 中的所有值都是 0。
'''
class Solution:
def lenLongestFibSubseq(self, arr: List[int]) -> int:
indices = {x: i for i, x in enumerate(arr)}
ans, n = 0, len(arr)
dp = [[0] * n for _ in range(n)]
for i, x in enumerate(arr):
for j in range(n - 1, -1, -1):
if arr[j] * 2 <= x:
break
if x - arr[j] in indices:
k = indices[x - arr[j]]
dp[j][i] = max(dp[k][j] + 1, 3)
ans = max(ans, dp[j][i])
return ans
golang 解法, 执行用时: 248 ms, 内存消耗: 17.5 MB, 提交时间: 2022-11-22 15:46:40
func lenLongestFibSubseq(arr []int) (ans int) {
n := len(arr)
indices := make(map[int]int, n)
for i, x := range arr {
indices[x] = i
}
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
for i, x := range arr {
for j := n - 1; j >= 0 && arr[j]*2 > x; j-- {
if k, ok := indices[x-arr[j]]; ok {
dp[j][i] = max(dp[k][j]+1, 3)
ans = max(ans, dp[j][i])
}
}
}
return
}
func max(a, b int) int {
if b > a {
return b
}
return a
}