Subsequence with difference of 1

Given a list of numbers, find the longest subsequence such that the absolute difference between adjacent elements is 1.

Hint

This algorithm finds the longest sequence of numbers in a list where each number differs from its adjacent one by exactly 1. For each number in the list, consider two options:

• Skip: Exclude the current number from the subsequence and proceed to the next number in the list.
• Take: Include the current number in the subsequence, if 'prev' is -1 or the absolute difference between the current number and the previous number in the subsequence is 1. If the "take" option is chosen, increment the length of the current subsequence by 1, update the 'prev' to the current indexm and ontinue to the next number in the list.

Return the maximum length of all the subsequences found during the recursive exploration.

• Python
• Javascript
•  Run

def count(ls, i, prev):
  if i >= len(ls):
    return 0

  skip = count(ls, i + 1, prev)
  
  take = 0

  if prev == -1 or abs(ls[i] - ls[prev]) == 1:
    take = 1 + count(ls, i + 1, i)

  return max(skip, take)

ls = [10, 9, 4, 5, 4, 8, 6]

print(count(ls, 0, -1))

function count(list, i, prev) {
  if (i >= list.length) {
    return 0;
  }

  let skip = count(list, i + 1, prev);

  let take = 0;
  if (prev === -1 || Math.abs(list[i] - list[prev]) === 1) {
    take = 1 + count(list, i + 1, i);
  }

  return Math.max(skip, take);
}

const list = [10, 9, 4, 5, 4, 8, 6];

console.log(count(list, 0, -1));