Write a function which, given an array of integers, returns the length of the longest subsequence where every next value is 1 bigger than the previous one. The subsequence might not be consecutive, but must be in the same order as the given array.
Example:
Input: 2 1 3 2 4 3 2 5 4 5
Output: 5This problem asks for the length of the longest subsequence that keeps the original order and increases by exactly 1 at each step. A standard solution uses dynamic programming with a hash map: for each value x, store the best length of a valid subsequence ending at x, and update it from the best sequence ending at x – 1. Scanning the array once is enough to compute the maximum length. In the sample, the longest valid subsequence has length 5.
END
