Longest Arithmetic Subsequence
Medium · Dynamic Programming · Array · Hash Table · Binary Search · Dynamic Programming
Problem
Given an integer array nums, return the length of its longest arithmetic subsequence.
A subsequence keeps the original order but may skip elements. A sequence is arithmetic when every element minus the one before it gives the same value, the step. The step may be zero or negative.
Examples
Input: nums = [1,7,3,5,10,5,7] Output: 4
1, 3, 5, 7 (indices 0, 2, 3, 6) has step 2.
Input: nums = [10,8,6,4,20] Output: 4
10, 8, 6, 4 has step −2.
Input: nums = [3,6,3,9,3,3] Output: 4
The four 3s form a sequence with step 0.
Constraints
- 2 <= len(nums) <= 1500
- 0 <= nums[i] <= 500
Approaches
- Baseline: fix the first two elements, then extend greedily — time O(n³), space O(1)
Follow-up
If the step were fixed in advance, one map from value to the best length ending at that value would give an O(n) answer. Here every step is possible, which is why each index needs its own table of steps and the work is O(n²).
Related problems
Start free on Cariara · Coding problems · System design studio
