This problem asks us to find the longest subsequence (not subarray) where the difference between consecutive elements is constant. The subsequence does not need to be contiguous, which makes it harder than finding arithmetic subarrays.

An arithmetic subsequence is fully described by two things: where it ends and its common difference. Once both are fixed, extending the subsequence means finding an earlier element that sits exactly one step (the common difference) below the current one. That framing drives both approaches below.

Key Constraints

Intuition

A pair of indices already determines a common difference. Pick two indices i and j with i < j, set d = nums[j] - nums[i], then walk forward from j + 1 and greedily take the next element equal to the last value plus d.

The greedy forward scan is safe here because the next value the chain needs, last + d, is a single fixed number. Any element equal to it extends the chain by one, and taking the earliest one leaves the most array left to extend further. So scanning left to right and grabbing the first match never undercounts.

Algorithm

Example Walkthrough

Input:

We start with maxLen = 2 and try every pair.

Every remaining pair gives length 2, so the answer is 3.

Code

The forward scan repeats work: every pair rescans the tail of the array. The next approach removes that scan by storing, for each index and each common difference, how long a chain already ends there. Extending then becomes a single lookup.

Intuition

If we already know the longest arithmetic subsequence ending at index j with common difference d, then any later index i with nums[i] - nums[j] == d extends it by one in O(1) time. We do not need to rescan anything.

Define dp[i] as a hash map where dp[i][d] holds the length of the longest arithmetic subsequence that ends at index i and has common difference d. Iterating j over all earlier indices for each i fills these maps, and the largest value across all of them is the answer.

Algorithm

Example Walkthrough

Code