Longest Subsequence With Steps of 0 or 1
You are given an integer array nums.
A subsequence keeps some of the elements in their original order. It does not need to use neighbouring positions.
Find the longest subsequence where every two next-to-each-other elements of the subsequence differ by 0 or 1. In other words, |a - b| <= 1 for each pair of neighbours a, b in the subsequence.
Return the length of that subsequence. A single element is always valid, so the answer is at least 1.
For each element, ask: what is the longest valid subsequence that ends with this element? It can only follow an earlier element whose value is x - 1, x or x + 1. Keep the best length for each value in a map.
Examples
Example 1
- Input:
- [4,5,9,4,3,4]
- Output:
- 5
Take 4, 5, 4, 3, 4 (skip the 9). Each step changes the value by exactly 1.
Example 2
- Input:
- [6,6,6]
- Output:
- 3
Equal neighbours differ by 0, which is allowed, so all three elements can be used.
Example 3
- Input:
- [2,8,3,9,4]
- Output:
- 3
2, 3, 4 is valid and has length 3. The values 8, 9 give only length 2.
Constraints
1 <= nums.length <= 15-10 <= nums[i] <= 10
Run checks your code against the 3 examples. Submit checks it against all 303 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.