如果序列 X_1, X_2, …, X_n 满足下列条件，就说它是 斐波那契式 的：
n >= 3
对于所有 i + 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] 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/Q91FMA
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
contains()
1.暴力解法
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int size = arr.length;
Set<Integer> set = new HashSet<>();
for(int num:arr){
set.add(num);
}
int maxL = 0;
for(int i =0;i<size;i++){
for(int j = i+1;j<size;j++){
int f= arr[i];
int s =arr[j];
int len = 2;
while(set.contains(f+s)){
s = f+s;
f= s-f;
len++;
}
if(len>maxL) maxL=len;
}
}
return maxL>=3?maxL:0;
}
}
dp+双指针
动态规划首先要找出状态的定义和状态转移公式。定义dp[i][j]表示以A[i]和A[j]结尾的斐波那契数列的最大长度。也就是[……，A[i]，A[j]]构成的斐波那契数列的最大长度。
状态转移公式就是，如果以A[i]和A[j]结尾能构成斐波那契数列，那么在这个数列A[i]之前必定有一个值A[k]满足A[k]+A[i]=A[j]；所以如果确定了A[i]和A[j]的值之后，我们可以往前来找A[k]，那么转移公式就是
dp[i][j]=dp[k][i]+1;
1 public int lenLongestFibSubseq(int[] A) {
2 //记录最大的斐波那契数列的长度
3 int maxLength = 0;
4 int length = A.length;
5 int[][] dp = new int[length][length];
6 for (int j = 2; j < length; j++) {//确定A[j]
7 for (int i = j - 1; i > 0; i--) {//确定A[i]
8 for (int k = i - 1; k >= 0; k--) {//往前查找A[k]
9 if (A[k] + A[i] == A[j]) {
10 dp[i][j] = dp[k][i] + 1;
11 //如果找到就终止内层循环，不在往前查找了
12 break;
13 } else if (A[k] + A[i] < A[j]) {
14 //题中说了是递增的正整数数组，如果当前A[k]
15 //小了，那么前面的就更小，没有合适的，没必要
16 //在往前找了，直接终止内层循环
17 break;
18 }
19 }
20 maxLength = Math.max(maxLength, dp[i][j]);
21 }
22 }
23 //注意数列长度统计的时候没有统计前面两项，如果能构成
24 //斐波那契数列最后还需要加上
25 return maxLength > 0 ? maxLength + 2 : 0;
26}
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int maxL = 0;
int length = arr.length;
int[][] dp = new int[length][length];
for(int j=2;j<length;j++){
int l=0;
int r= j-1;
while(l<r){
int sum = arr[l]+arr[r];
if(sum>arr[j]){
r--;
}else if(sum<arr[j]){
l++;
}else{
dp[r][j] = dp[l][r] +1;
maxL = Math.max(maxL,dp[r][j]);
r--;
l++;
}
}
}
return maxL>0?maxL+2:0;
}
}