313. Longest Subsequence With Adjacent Elements Differing by One

Given an array of n integers, find the length of the longest subsequence such that every pair of consecutive elements in the subsequence has an absolute difference of exactly 1.

Input: The first line contains an integer n. The second line contains n space-separated integers, the array. Output: Print a single integer - the length of the longest subsequence where every consecutive pair differs by exactly 1.

1 <= n <= 10^4

Unlike strict LIS, this allows EITHER direction (predecessor can be one LESS or one MORE than the current element) - the absolute-value check |arr[j]-arr[i]|==1 correctly captures both cases in a single condition.

Find the length of the longest subsequence where every pair of consecutive elements differs by exactly 1. Brute force: Try every possible subsequence directly and check the adjacent-difference-of-1 constraint, taking the longest - this is exponential (2^n subsequences), impractical for n up to 10^4. Optimised: This follows the exact same DP shape as Longest Increasing Subsequence - the only change is the compatibility test between a candidate predecessor and the current element (exact difference of 1, instead of strictly less than) - recognizing this shared structure lets you directly reuse the O(n²) LIS technique.

Generate every possible subsequence of the array by deciding, for each element, whether to include or exclude it, and for each generated subsequence check whether every pair of consecutive chosen elements differs by exactly 1, keeping track of the longest valid one found. Since there are 2^n possible subsequences, this exhaustive check is only feasible for very small n. Time: O(2^n) Space: O(n)

Since what matters is the actual numeric value at each position rather than its index, maintain a hash map from a value v to the length of the longest valid subsequence seen so far that ends in a number equal to v. Process the array left to right; for each element a[i], its best subsequence length ending at this value is 1 plus the better of whatever is already recorded for value a[i]-1 or a[i]+1, and update the map entry for a[i] with this new best if it improves on what is stored. This replaces the quadratic backward search with constant hash map work per element. Time: O(n) Space: O(n)

Define dp[i] as the length of the longest valid subsequence ending at index i. To compute dp[i], look back at every earlier index j < i, and whenever the absolute difference between a[i] and a[j] is exactly 1, dp[i] can potentially become dp[j] + 1; take the best such option over all valid j (or 1 if none qualify). The answer is the maximum dp value across all indices, and since every index is compared against every earlier index, this takes quadratic time. Time: O(n^2) Space: O(n)

1. dp[i] = length of the longest valid subsequence ENDING exactly at index i; initialize every dp[i]=1. 2. For each i, check every earlier index j: if |arr[j]-arr[i]|==1, dp[i]=max(dp[i], dp[j]+1). 3. The answer is the maximum value anywhere in the dp array.

Time: O(n²) - for each index i, checking all earlier indices j. Space: O(n), for the dp array.

Test n = 1 (answer 1), an array with repeated/duplicate values (as in the example, where 4 appears twice), and n at the upper bound of 10^4 for the O(n^2) DP.

Be ready to recognize and state this immediately as 'LIS with a different compatibility condition' - this exact pattern (same DP skeleton, swap out the comparison test) appears repeatedly across this category's subsequence problems (Maximum Length Chain of Pairs being another example).