Medium Problemsoptimizationlinear

Longest Subsequence with 1 adjacent difference

Given an array of integers, find the length of the longest subsequence in which every pair of consecutive chosen values differs by exactly 1.

Do this lesson first: house robber

Example input

nums = [1, 100, 2, 99, 3, 98, 4, 97, 5, 96, 6, 95]

Expected output

6

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = 1 + max over every j < i with abs(nums[i] - nums[j]) == 1 of dp[j], or 1 if no such j exists

Ask what value sat immediately before this one in the best run that ends at index i. It has to be some earlier index whose value is exactly one away, either one higher or one lower, since that is the run's only rule; whichever qualifying earlier index already holds the longest run is the one to extend. Every qualifying j is a candidate to extend, compared rather than summed, since only one of them actually precedes index i in the run that ends here.

dp[0] = 1 is the only declared base: with no index before 0, the first element trivially starts a run of length 1 by itself, and it does get read later, at index 2, since nums[2] = 2 is exactly 1 away from nums[0] = 1. Every other index is a genuine compute cell, even the ones with no qualifying predecessor at all: dp[1] is exactly that case, since nums[0] = 1 is 99 away from nums[1] = 100, nowhere near a difference of exactly 1, so dp[1] resolves to 1 on the strength of the same plus-one for standing alone, with no cell_read emitted, because there is nothing one-away before it to consult. Every other cell depends only on smaller indices, so filling left to right guarantees every predecessor that does qualify already holds a real value before it is read. Because the answer is whichever cell ends up largest, not necessarily the last one, the table also has to track that argmax as it fills.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 1 is the only declared base: with no index before 0, the first element trivially starts a run of length 1 by itself, and it does get read later, at index 2, since nums[2] = 2 is exactly 1 away from nums[0] = 1. Every other index is a genuine compute cell, even the ones with no qualifying predecessor at all: dp[1] is exactly that case, since nums[0] = 1 is 99 away from nums[1] = 100, nowhere near a difference of exactly 1, so dp[1] resolves to 1 on the strength of the same plus-one for standing alone, with no cell_read emitted, because there is nothing one-away before it to consult. Every other cell depends only on smaller indices, so filling left to right guarantees every predecessor that does qualify already holds a real value before it is read. Because the answer is whichever cell ends up largest, not necessarily the last one, the table also has to track that argmax as it fills.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

i=9

i=10

i=11

1

2

3

4

5

6

longest-subsequence-with-adjacent-difference-one.ts

1function longestSubsequenceAdjacentDiffOne(nums) {
2 const dp = new Array(nums.length).fill(1);
3 let best = dp[0];
4 for (let i = 1; i < nums.length; i++) {
5 for (let j = 0; j < i; j++) {
6 if (Math.abs(nums[i] - nums[j]) === 1) dp[i] = Math.max(dp[i], dp[j] + 1);
7 }
8 best = Math.max(best, dp[i]);
9 }
10 return best;
11}

Base caseComputedBeing readAnswer

The code, the trap, the variations

longest-subsequence-with-adjacent-difference-one.ts

1function longestSubsequenceAdjacentDiffOne(nums) {
2 const dp = new Array(nums.length).fill(1);
3 let best = dp[0];
4 for (let i = 1; i < nums.length; i++) {
5 for (let j = 0; j < i; j++) {
6 if (Math.abs(nums[i] - nums[j]) === 1) dp[i] = Math.max(dp[i], dp[j] + 1);
7 }
8 best = Math.max(best, dp[i]);
9 }
10 return best;
11}

Where people go wrong

Assuming the chosen values must sit next to each other in the array. They do not: here the two runs that actually differ by 1 (1, 2, 3, 4, 5, 6 and 100, 99, 98, 97, 96, 95) are interleaved one element apart the whole way through, so the longest subsequence has to skip every other element to stay on one run. A second version of the same mistake is reading the last cell as the answer instead of the largest cell in the table; both runs finish with a table value of 6, but the ascending run's tail reaches it one index earlier.

Return one such subsequence itself, not just its length.
Each cell would need to remember which earlier index it extended, so the subsequence can be walked backward from the best cell once found; the length recurrence and the left-to-right order do not change at all.
Require every consecutive pair to differ by exactly k instead of exactly 1.
Only the single comparison changes, from abs(nums[i] - nums[j]) == 1 to abs(nums[i] - nums[j]) == k; the plus-one, the max over qualifying j, and the argmax-over-the-table answer all stay exactly the same.

Arrange Balls with adjacent of different types Maximum size square sub-matrix with all 1s