главная новое лучшее написать
▲
3
▼

🚀 Двунаправленный итератор + оптимизированный ДП для поиска самой длинной фибоначчиевой подпоследовательности
leetcoder, 27-02-2025 , 181

Ссылка на задачу — 873. Length of Longest Fibonacci Subsequence.

📌 Описание задачи

Дан монотонно возрастающий массив arr. Нужно найти длину самой длинной фибоначчиевой подпоследовательности, где каждые три последовательных элемента x, y, z удовлетворяют свойству: z = x + y

Если такой подпоследовательности нет, вернуть 0.

💡 Идея

📌 Подробности метода

  1. Перебираем z = arr[k], начиная с k = 2, так как нужны минимум 3 числа.
  2. Будем использовать два указателя (front и back) на arr[..k]:
    • front движется вперёд (x увеличивается).
    • back движется назад (y уменьшается).
  3. Сравниваем x + y и z:
    • Если x + y == z:
      • обновляем dp[z, y] = dp[y, x] + 1 (или (2+1), если dp[y,x] пусто);
      • двигаем оба указателя.
    • Если x + y > z, сдвигаем back (уменьшаем y).
    • Если x + y < z, сдвигаем front (увеличиваем x).
  4. Возвращаем ответ как максимум по всем dp[z,y].

📊 Асимптотика

📜 Исходный код

use std::collections::HashMap;
use std::cmp::Ordering;

impl Solution {
    pub fn len_longest_fib_subseq(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut dp: HashMap<(i32, i32), i32> = HashMap::new(); // DP map to store sequence lengths

        // Iterate over each element z as the potential end of a Fibonacci-like sequence
        for k in 2..n {
            let z = arr[k];
            let mut xy_vals = arr[..k].iter();
            let mut front = xy_vals.next();
            let mut back = xy_vals.next_back();

            while let (Some(&x), Some(&y)) = (front, back) {
                match (x + y).cmp(&z) {
                    Ordering::Equal => {
                        // Apply DP transition rule: dp[z, y] = dp[y, x] + 1
                        let cur_len = dp.get(&(y, x)).unwrap_or(&2) + 1;

                        // Store length of subsequence ending at (z, y)
                        dp.insert((z, y), cur_len);

                        // Move both pointers
                        front = xy_vals.next();
                        back = xy_vals.next_back();
                    }
                    Ordering::Less => { front = xy_vals.next(); }        // Move x (front)
                    Ordering::Greater => { back = xy_vals.next_back(); } // Move y (back)
                }
            }
        }

        *dp.values().max().unwrap_or(&0)
    }
}

Tags: #rust #algorithms #dp

▲ 1 ▼ leetcoder 27-02-2025

Интересным выглядит способ, как красиво декомпозировать решение.
Для этого мы выделим итератор по всем кортежам {(x,y) | x+y=z} в отдельный метод.

use std::collections::HashMap;
use std::cmp::Ordering;

impl Solution {
    pub fn len_longest_fib_subseq(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut dp: HashMap<(i32, i32), i32> = HashMap::new(); // DP table storing lengths of valid subsequences

        // Iterate over each element z as a potential end of a Fibonacci-like sequence
        for k in 2..n {
            let z = arr[k];

            // Use an iterator to find all valid pairs (x, y) where x + y = z
            for (x, y) in Self::pair_sum_iterator(arr[..k].iter(), z) {
                // Apply DP transition: dp[z, y] = dp[y, x] + 1, defaulting to 2 if not found
                let cur_len = dp.get(&(y, x)).unwrap_or(&2) + 1;

                // Store computed length for (z, y)
                dp.insert((z, y), cur_len);
            }
        }

        // Return the longest found subsequence length, or 0 if none exist
        *dp.values().max().unwrap_or(&0)
    }

    /// A helper function that iterates over pairs (x, y) in a sorted array slice,
    /// finding pairs where x + y == target_sum using a two-pointer approach.
    fn pair_sum_iterator<'a>(mut iter: impl DoubleEndedIterator<Item = &'a i32>, target_sum: i32) -> impl Iterator<Item = (i32, i32)> {
        std::iter::from_fn(move || {
            let mut front = iter.next();
            let mut back = iter.next_back();

            while let (Some(&x), Some(&y)) = (front, back) {
                match (x + y).cmp(&target_sum) {
                    Ordering::Equal => return Some((x, y)), // Found a valid pair (x, y)
                    Ordering::Less => front = iter.next(),  // Increase x to increase the sum
                    Ordering::Greater => back = iter.next_back(), // Decrease y to reduce the sum
                }
            }
            None
        })
    }
}
ответить