Pattern visualizer
Longest Arithmetic Subsequence
A subsequence only cares about two things at its growing tip: which index it currently ends at, and the common difference it has committed to. So dp[i][d] tracks the longest chain ending at index i with difference d. To extend it, look one step further back: any earlier index j with nums[i] - nums[j] = d hands its own dp[j][d] forward, plus one for the element just added. When no earlier index has used that difference yet, the pair (j, i) simply starts a brand-new chain of length 2 — every arithmetic subsequence has to start somewhere. Animated on: nums = [3,6,9,12,15] — find the length of the longest arithmetic subsequence (elements need not be contiguous, but a constant difference must hold between consecutive picks)..
dp[i][d] = dp[j][d] + 1 when nums[i] - nums[j] = d
dp[i][d] = longest chain ending at index i with common difference d
nums[0]=3 and nums[1]=6 differ by 3, a difference index 0 has never used, so this starts a fresh 2-element chain: dp[1][3] = 2.
1FUNCTION longestArithSeqLength(nums):2 n <- LENGTH(nums)3 ans <- 14 dp <- ARRAY OF n EMPTY MAPS5 FOR i FROM 1 TO n-1:6 FOR j FROM 0 TO i-1:7 d <- nums[i] - nums[j]8 dp[i][d] <- dp[j].GET(d, 1) + 19 ans <- MAX(ans, dp[i][d])10 RETURN ans
← / → step · space play · Home restart