楼主:
Rushia (みけねこ的鼻屎)
2025-02-28 01:09:24https://leetcode.com/problems/length-of-longest-fibonacci-subsequence
873. Length of Longest Fibonacci Subsequence
给你一个阵列arr,该阵列所有元素都严格递增,找出一个最长子序列每个数字都是费波那
契数,返回该序列的长度。
思路:
姆咪卡了好久,总之就是先固定序列的后两个数字假设位置为i和j(i>j),然后往前找一个
k满足:
1.arr[k] = arr[i] - arr[j]
2.k < j
所以就用一个map纪录每个数字的索引在哪,然后固定i和j,检查有没有k满足条件,有的
话就把序列长度+1,用一个二维的dp[i][j]阵列保存以i和j为结尾的最长序列长,为了方
便计算初始值为2,返回最大的dp[i][j]就好。
Java Code: