## 873. Length of Longest Fibonacci Subsequence

A sequence `X1, X2, ..., Xn` is Fibonacci-like if:

• `n >= 3`
• `Xi + Xi+1 = Xi+2` for all `i + 2 <= n`

Given a strictly increasing array `arr` of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of `arr`. If one does not exist, return `0`.

A subsequence is derived from another sequence `arr` by deleting any number of elements (including none) from `arr`, without changing the order of the remaining elements. For example, `[3, 5, 8]` is a subsequence of `[3, 4, 5, 6, 7, 8]`.

Example 1:

```Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: The longest subsequence that is fibonacci-like: [1,2,3,5,8].```

Example 2:

```Input: arr = [1,3,7,11,12,14,18]
Output: 3
Explanation: The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].```

Constraints:

• `3 <= arr.length <= 1000`
• `1 <= arr[i] < arr[i + 1] <= 109`

## Rust Solution

``````struct Solution;
use std::collections::HashSet;

impl Solution {
fn len_longest_fib_subseq(a: Vec<i32>) -> i32 {
let n = a.len();
let mut hs: HashSet<i32> = HashSet::new();
for &x in &a {
hs.insert(x);
}
let mut max = 0;
let last = a[n - 1];
for i in 0..n {
for j in i + 1..n {
let mut small = a[i];
let mut big = a[j];
let mut sum = small + big;
let mut size = 0;
if big * max > last {
break;
}
while hs.contains(&sum) {
small = big;
big = sum;
sum = small + big;
size += 1;
}
max = max.max(size);
}
}
if max > 0 {
(max + 2) as i32
} else {
0
}
}
}

#[test]
fn test() {
let a = vec![1, 2, 3, 4, 5, 6, 7, 8];
let res = 5;
assert_eq!(Solution::len_longest_fib_subseq(a), res);
let a = vec![1, 3, 7, 11, 12, 14, 18];
let res = 3;
assert_eq!(Solution::len_longest_fib_subseq(a), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.