DSA Tracker

Visualize

Longest Arithmetic Subsequence

dp[i][d] = dp[j][d] + 1 when nums[i] - nums[j] = d

time O(n^2)space O(n^2)

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.

Details

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).

Problem:Longest Arithmetic SubsequenceMedium

dp[i][d] = dp[j][d] + 1 when nums[i] - nums[j] = d

step 1 / 11

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.

Pseudocode
1FUNCTION longestArithSeqLength(nums):
2  n <- LENGTH(nums)
3  ans <- 1
4  dp <- ARRAY OF n EMPTY MAPS
5  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) + 1
9      ans <- MAX(ans, dp[i][d])
10  RETURN ans

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. 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.
  2. nums[0]=3 and nums[2]=9 differ by 6, a difference index 0 has never used, so this starts a fresh 2-element chain: dp[2][6] = 2.
  3. nums[1]=6 and nums[2]=9 share difference 3 with the chain already ending at index 1 (length 2), so it extends: dp[2][3] = 2 + 1 = 3.
  4. nums[0]=3 and nums[3]=12 differ by 9, a difference index 0 has never used, so this starts a fresh 2-element chain: dp[3][9] = 2.
  5. nums[1]=6 and nums[3]=12 differ by 6, a difference index 1 has never used, so this starts a fresh 2-element chain: dp[3][6] = 2.
  6. nums[2]=9 and nums[3]=12 share difference 3 with the chain already ending at index 2 (length 3), so it extends: dp[3][3] = 3 + 1 = 4.
  7. nums[0]=3 and nums[4]=15 differ by 12, a difference index 0 has never used, so this starts a fresh 2-element chain: dp[4][12] = 2.
  8. nums[1]=6 and nums[4]=15 differ by 9, a difference index 1 has never used, so this starts a fresh 2-element chain: dp[4][9] = 2.
  9. nums[2]=9 and nums[4]=15 share difference 6 with the chain already ending at index 2 (length 2), so it extends: dp[4][6] = 2 + 1 = 3.
  10. nums[3]=12 and nums[4]=15 share difference 3 with the chain already ending at index 3 (length 4), so it extends: dp[4][3] = 4 + 1 = 5.
  11. dp[4][3] = 5 is the largest value anywhere in the table — the longest arithmetic subsequence has length 5.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest Arithmetic Subsequence in the editorAll Dynamic Programming problemsBack to roadmap