DSA problem
Longest Arithmetic Subsequence
Given an array nums of integers, return the length of the longest arithmetic subsequence in nums. A subsequence is derived by deleting zero or more elements without changing the order of the remaining ones. An arithmetic subsequence is one whose consecutive differences are all the same constant d.
Unlike a contiguous arithmetic slice problem, here the elements may be far apart in the original array. The common difference d can be any integer (positive, zero, or negative), so we cannot enumerate d cheaply ahead of time. A pure O(n²) length-DP on indices alone does not work because the recurrence depends on which common difference is being extended.
The trick is to keep, for every index i, a hash map dp[i] keyed by common difference d whose value is the length of the longest arithmetic subsequence ending at index i with that difference. For every pair j < i, compute d = nums[i] - nums[j]. If an arithmetic subsequence ending at j with difference d already exists, extend it: dp[i][d] = dp[j][d] + 1. Otherwise we are starting a new two-element subsequence [nums[j], nums[i]] so dp[i][d] = 2.
The final answer is the maximum value found in any dp[i][d] over the entire computation. The algorithm runs in O(n²) time and O(n²) space in the worst case, which is sufficient for the typical constraint n <= 1000.
Examples
nums = [3,6,9,12]4nums = [9,4,7,2,10]3nums = [20,1,15,3,10,5,8]4Constraints
- 2 <= nums.length <= 1000
- 0 <= nums[i] <= 500
- The common difference d can be any integer.
- The subsequence does not need to be contiguous.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.