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
 */

use std::collections::HashMap;

impl Solution {
  pub fn len_longest_fib_subseq(arr: Vec<i32>) -> i32 {
    let n = arr.len();
    let idx: HashMap<i32, usize> = arr.iter().enumerate().map(|(i, &v)| (v, i)).collect();
    // dp[i][j] = length of longest fib-subseq ending with arr[i], arr[j]
    let mut dp = vec![vec![0i32; n]; n];
    let mut ans = 0;
    for j in 0..n {
      for k in (j+1)..n {
        let need = arr[k] - arr[j];
        if need < arr[j] {
          if let Some(&i) = idx.get(&need) {
            dp[j][k] = dp[i][j].max(2) + 1;
            ans = ans.max(dp[j][k]);
          }
        }
      }
    }
    if ans >= 3 { ans } else { 0 }
  }
}