## 873. Length of Longest Fibonacci Subsequence

A sequence `X`

is _{1}, X_{2}, ..., X_{n}*Fibonacci-like* if:

`n >= 3`

`X`

for all_{i}+ X_{i+1}= X_{i+2}`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:5Explanation:The longest subsequence that is fibonacci-like: [1,2,3,5,8].

**Example 2:**

Input:arr = [1,3,7,11,12,14,18]Output:3Explanation: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] <= 10`

^{9}

## 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.