873. Length of Longest Fibonacci Subsequence
A sequence X1, X2, ..., Xn is Fibonacci-like if:
n >= 3Xi + Xi+1 = Xi+2for alli + 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 <= 10001 <= 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.