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. It compares each number in the list to the previous number in the sequence. Two choices:

• Take: If the difference between the current number and the previous number in the sequence is 1, add the current number to the sequence and move to the next one by calling 1 + call of moving to the next one.
• Skip: If the difference is not 1, skip the current number and return call of moving to the next one.

Repeats these steps for each number in the list, selects the count that results in the longest subsequence. To keep track of the sequence, the algorithm "remembers" the last number added to the sequence.

• Python
• Javascript
•  Run

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

  take = 0

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

  skip = count(ls, i + 1, last)

  return max(skip, take)

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

print(count(ls, 0, 0))

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

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

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

  return Math.max(skip, take);
}

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

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