Longest Arithmetic Subsequence
Longest Arithmetic Subsequence: return the length of the longest subsequence of nums whose consecutive elements differ by a constant.
- 2 <= nums.length <= 1000
- 0 <= nums[i] <= 500
Intuition
A subsequence is only extendable if you know its common difference, so the state must include it. For each index keep a map from difference to the best run ending there — then extending is a lookup: whatever ran into j with difference d can absorb i and grow by one.
When 'valid extension' depends on a property fixed earlier in the sequence, that property becomes part of the DP state. The tell is a constraint between consecutive chosen elements that is not derivable from the last one alone — here the common difference, hence a map per index rather than a scalar.
Approach
Before reading on: why is dp[i] alone — the longest run ending at i — not enough information to decide whether a later element extends it? What must be stored alongside? Aim for O(n²).
The state needs a difference, not just an index
Longest Increasing Subsequence gets away with dp[i] alone because 'increasing' is checkable from two values. Here 'arithmetic' depends on a difference that was fixed earlier in the run, so dp[i] cannot say whether nums[i] extends anything. The state must be a pair — index plus difference — which is why each index carries a dictionary rather than a single number.
The transition
For every pair j < i, compute d = nums[i] - nums[j]. If index j already has a run with difference d of length L, then appending nums[i] gives L + 1. If not, nums[j] and nums[i] alone form a run of 2. Written as dp[i][d] = dp[j].get(d, 1) + 1, the default of 1 elegantly encodes 'j starts a fresh pair' — the single element at j, plus i, makes two. Track the running maximum as you fill.
Cost and why binary search does not help
The double loop over pairs is O(n²), and each map operation is O(1), so the total is O(n²) time and O(n²) space in the worst case — every index can hold up to n distinct differences. With n ≤ 1000 that is a million entries, which is fine. Unlike Longest Increasing Subsequence, there is no O(n log n) improvement here: the patience-sorting trick relies on a total order over run endings, and runs with different common differences are not comparable.
Solution & live demo
Common pitfalls
Defaulting the lookup to 0
dp[i][diff] = dp[j].get(diff, 0) + 1
dp[i][diff] = dp[j].get(diff, 1) + 1
When j has no run with this difference, j itself is still an element — it and i form a pair of length 2. Defaulting to 0 reports 1 and undercounts every fresh run.
Using a single value per index
dp = [1] * n dp[i] = dp[j] + 1
dp = [dict() for _ in range(n)]
Without the difference in the state, runs with incompatible differences get chained together — the code happily extends a +2 run with a +5 step and reports impossible lengths.
Initialising best to 1 or 0
best = 0
best = 2
The constraints guarantee at least two elements, and any two form an arithmetic sequence. Starting below 2 returns a smaller answer on arrays where no longer progression exists.
Edge cases
The difference is 0, which is a valid arithmetic progression, so the answer is the array length.
Any two values form an arithmetic sequence, so the answer is 2.
The default of 2 from any pair is the answer.
Differences are used as dictionary keys, so sign is irrelevant.
Each pair produces its own difference entry; duplicates simply create zero-difference runs.