Longest Arithmetic Subsequence

Problem

Given an integer array nums, return the length of the longest subsequence in which consecutive elements have the same difference. A subsequence keeps the original order but may skip elements; a sequence a_0, a_1, ..., a_k is arithmetic when a_{i+1} - a_i is the same value for every i. Any subsequence of length 1 or 2 is arithmetic by definition.

• nums holds up to about a thousand integers.
• Each value is a non-negative integer no larger than a few hundred.

Examples

• nums = [2, 6, 10, 14] → 4. The whole array has difference 4.
• nums = [8, 3, 6, 1, 9] → 3. 3, 6, 9 has difference 3.
• nums = [16, 1, 12, 3, 8, 5, 7] → 4. 1, 3, 5, 7 has difference 2.

Hints

1. An arithmetic subsequence is determined by where it ends and what its difference is. Fix both and ask how it could have been built.
2. For a subsequence ending at index i with difference d, the element before the last must be at some j < i with nums[j] = nums[i] - d.
3. DP with state (index, difference): length[i][d] = length[j][d] + 1 for each j < i, d = nums[i] - nums[j], stored in a dictionary or a dense table over the difference range.