作者:
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: