RUST GYM v0.2.4

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.