Longest arithmetic subsequence

Array Hash Table Binary Search Dynamic Programming

49.9% acceptance

Feb 25, 2026

4904

220

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums. Note that: A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements. A sequence seq is arithmetic if seq[i + 1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_arith_seq_length(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut dp: Vec<std::collections::HashMap<i32,i32>> = vec![std::collections::HashMap::new(); n];
    let mut ans = 2;
    for i in 1..n {
      for j in 0..i {
        let diff = nums[i] - nums[j];
        let prev = *dp[j].get(&diff).unwrap_or(&1);
        let cur = dp[i].entry(diff).or_insert(1);
        *cur = (*cur).max(prev + 1);
        ans = ans.max(*cur);
      }
    }
    ans
  }
}