mediumDynamic Programming 1DPure DSA~30 min
Longest Arithmetic Subsequence
Find the longest run of values — not necessarily adjacent — that forms an arithmetic progression, the basis of trend-spotting in a metric series.
Problem
Given an integer array nums, return the length of the longest arithmetic subsequence: a subsequence (order preserved, gaps allowed) where the difference between consecutive elements is constant.
Input
An integer array nums.
Output
An integer: the length of the longest arithmetic subsequence.
Constraints
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 500
Examples
Example 1
Input
nums = [3,6,9,12]
Output
4
The whole array is arithmetic with common difference 3.
Example 2
Input
nums = [9,4,7,2,10]
Output
3
[4,7,10] is an arithmetic subsequence of length 3.