O(N * M) | DP | Best tail sequences for each number / difference pair
IntuitionThe key observation here is the limited number of distict values in the array. Namely, at most 300 unique values are possible with 299 unique differenc
# Intuition

The key observation here is the limited number of distict values in the array. Namely, at most 300 unique values are possible with 299 unique difference values.

Given that, we can greedily try every possible `(possition, next_difference)` combination for every possible subseuence starting at `position`.

To implement this process we will try to prolong the current value `nums[i]` with every uniue number `nums[j]` from the right part of the array (at most 300 such numbers) and for the difference between these 2 values we will perform a constant time lookup in a special `array[difference] = sequence_length` stored for each `nums[j]`, which will tell us what's the best sequnce for the given parameters is. Then, we will index the current value and its `difference->length` mapping and repeat the process for the next position.

# Approach

Let's define `M` as the meximal number in the input array.

The `tails` variable will represent all possible next numbers for the current sequence. The format is `tails[next_value] = max_lengths_array`, where `max_lengths_array[diff] = length` denoting maximal length for a sequence starting with number `next_value` and having next difference no bigger than `diff`.

Traverse all numbers in the input array from the last value to the first one. For each value:
- Initialize its maximal lengths array `curr_diffs` as an array with `M` values `1`: `[1, 1, ..., 1]`. The meaning here is that the current number `nums[i]` can form a single value sequence `[X]` with imaginary differences 0, 1, etc.
- Then, for each previously seen number `nums[j]` stored as a key in `tails` check if the number can create a new bigger sequence starting at current value `nums[i]`. To do so, calculate the difference between these 2 numbers and check what's the best length we can by starting the tail sequence at `nums[j]`. That's exactly `tails[next_num][difference]`.
- Make sure `curr_diffs` is non-decreasing and every value is propagated until a longer sequence with a bigger difference is met. For example, if the found `(difference, legnth)` pairs were `(diff=0, len=1), (diff=3, len=2), (diff=5,len=3)` the state of `curr_diffs` would be: `[1, 1, 1, 2, 2, 3, 3, 3, 3, ..., 3]`. That's an important part to have constant time lookup num/diff lookups during next interations.
- Update the result if the maxiumal length in `curr_diffs` is bigger.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

$$O(N * M)$$ - we iterate over the input array of size `N` and perform at most `M` next number checks and non-decreasing difference array propagation operations

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(M * M)$$ - for each unique number (at most `M` values) we keep a length mapping for each possible difference (at most `M-1` values)

# Code
```python3 []
    def longestSubsequence(self, nums: List[int]) -> int:
        m = max(nums) + 1
        # tails[num][diff] = max_len
        tails = {}
        result = 0
        for num in reversed(nums):
            curr_diffs = [1] * m
            for next_num in tails:
                diff = abs(num - next_num)
                best_tail_len = tails[next_num][diff]
                curr_diffs[diff] = max(1 + best_tail_len, curr_diffs[diff])

            # making the diffs index non-decreasing
            for idx in range(1, len(curr_diffs)):
                curr_diffs[idx] = max(curr_diffs[idx-1], curr_diffs[idx])

            tails[num] = curr_diffs
            result = max(curr_diffs[-1], result)
        return result
```
['Dynamic Programming', 'Greedy', 'Python3']