Longest Subsequence with Adjacent Diff as 1

Problem Overview

Pick elements in input order, not by sorting.

Intuition

Pick elements in input order, not by sorting. The last chosen value decides what can follow: only x-1 or x+1. Track the longest chain ending at each value. When you see x again, extend from the best neighbor length already stored.

Algorithm

1Let dp[v] be the longest valid subsequence that ends with value v.
2Scan the array left to right.
3For each x, set dp[x] = 1 + max(dp[x-1], dp[x+1]).
4Keep the global maximum length seen.
5Return that maximum.

Example Walkthrough

Input: arr = [10, 9, 4, 5, 4, 8, 6]

1. Chains grow at 10, 9, then around 4 and 5.
2. Best length-3 paths include {10,9,8}, {4,5,4}, and {4,5,6}.
3. No chain of length 4 is possible.

Output: 3

Common Pitfalls

• Subsequence order follows the array. You cannot reorder values freely.
• A value may appear many times; each visit can extend a longer neighbor chain.
• A direct table by value is faster than a hash map when values are dense.
• Guard x-1 and x+1 at the ends of the value range if 0 or the max can appear.

Longest Subsequence with Adjacent Diff as 1.java

Java

// Approach: A subsequence ending at value x can extend from x-1 or x+1 seen earlier.
// Keep the best length per value in a direct table and update in one left-to-right pass.
// Complexity: O(n) time and O(max value) extra space.
class Solution {

    public int longestSubseq(int[] arr) {
        int[] dp = new int[1000001];
        int ans = 1;
        for (int x : arr) {
            dp[x] = 1 + Math.max(dp[x - 1], dp[x + 1]);
            ans = Math.max(ans, dp[x]);
        }

        return ans;
    }
}

Was this solution helpful?