一、題目
如果序列X_1, X_2, ..., X_n滿足下列條件，就說它是斐波那契式的：
條件1：n >= 3；
條件2：對于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}；
給定一個嚴(yán)格遞增的正整數(shù)數(shù)組形成序列arr，找到arr中最長的斐波那契式的子序列的長度。如果一個不存在，返回 0 。
回想一下，子序列是從原序列 arr 中派生出來的，它從 arr 中刪掉任意數(shù)量的元素（也可以不刪），而不改變其余元素的順序。例如， [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 <= 1000
1 <= arr[i] < arr[i + 1] <= 10^9
三、解題思路
如果大家對動態(tài)規(guī)劃比較熟悉，可以采用動態(tài)規(guī)劃進(jìn)行解題。奈何我這方面實在拉胯，理解不了這么高深的解題方式，所以，就以我自己方便理解的方式進(jìn)行的解題。不喜見諒，繞行勿噴。
話不多說，言歸正傳。我的解題思路是這樣的，既然想要獲取最長的斐波那契序列的長度，那么我們需要找出哪些序列是符合斐波那契數(shù)列的。由于是要滿足X_i + X_{i+1} = X_{i+2}，所以我們需要兩個指針來指向X_i和X_{i+1}，方便后續(xù)對這兩個值進(jìn)行計算。
這里有一個重要的條件，就是“給定一個嚴(yán)格遞增的正整數(shù)數(shù)組形成序列arr”，這個數(shù)組中的數(shù)字是遞增的。通過這個條件，我們其實可以確定一點，就是我們不需要從頭到尾的去遍歷，而只需要去遍歷到數(shù)組最大元素的1/2處即可，如下所示：
【注意】這里題目中的嚴(yán)格遞增，我不知道是不是排除掉了相同元素，例如：1,2,2,2這種。還是所有元素都要滿足a[i]一定小于a[i+1]，為了不糾結(jié)這個情況，所以直接把middle定位到了max的1/2加1的位置上了。
確定了middle的位置之后，其實還有一個需要注意的是，通過計算得出的X_{i+2}是不能大于max這個值的，所以，這也是我們遍歷中需要注意判斷的一點。
那么下面我們就來演示一下遍歷的具體流程，我們先從arr[0]和arr[1]這兩個位置開始，具體邏輯如下圖所示：
經(jīng)過第一次遍歷后，我們分別賦值了全新的num_a和num_b，那么繼續(xù)尋找斐波那契子序列，具體邏輯如下圖所示：
此時我們發(fā)現(xiàn)，num_a沒有超過middle，并且num_a與num_b相加也沒有超過max ，可以繼續(xù)查找斐波那契子序列，具體邏輯如下圖所示：
此時我們發(fā)現(xiàn)，num_a已經(jīng)等于middle了，不滿足小于middle的要求，所以終止尋找斐波那契子序列的操作，如下圖所示：
此時result等于3，這就是以arr[0]作為基準(zhǔn)的第一次遍歷結(jié)果。隨后，我們繼續(xù)以arr[1]作為基準(zhǔn)，再次按照上面的示例進(jìn)行循環(huán)，如果發(fā)現(xiàn)temp值大于result值了，那么則更新result值 。全部更新完畢，一定要記得，如果result不等于0，則返回值是result+2，因為只要匹配到了斐波那契子序列，最短的舉例就是3的長度，而我們上面邏輯中，如果找到了斐波那契子序列，result值賦值的是1，所以，最終結(jié)果要再加上2。當(dāng)然，如果沒有找到任何的斐波那契子序列，result直接返回0即可，也不需要加2了。
四、代碼實現(xiàn)
今天的文章內(nèi)容就這些了，最后一句話：
寫作不易，分文不取，陪伴成長，點贊分享。
更多技術(shù)文章，歡迎大家關(guān)注公眾號“爪哇繆斯”(o)/~
題目來源：力扣
