Longest Subsequence With Decreasing Adjacent Difference
IntuitionThe problem involves finding the longest subsequence in an array such that the difference between consecutive elements in the subsequence remains consi
# Intuition
The problem involves finding the longest subsequence in an array such that the difference between consecutive elements in the subsequence remains consistent. To solve this, we use dynamic programming to track the longest subsequence for each possible difference. The idea is to extend previous subsequences by adding the current number, while maintaining the same difference.

# Approach
1. Dynamic Programming Tables:
(a) g[x][d]: Tracks the maximum length of a subsequence ending with the number x and having a difference d between consecutive elements.
(b) f[d]: A temporary table for the current number x to calculate and store the maximum length for all differences d based on g.

2. Steps:
(a) Iterate over each number x in nums.
(b) For each potential previous number y (ranging from 1 to U):
(c) Calculate the absolute difference d = abs(x - y).
(d) Update f[d] to be the maximum of its current value and g[y][d] + 1, indicating the extension of a subsequence ending at y with difference d.
(e) Update g[x][d] based on the calculated values in f[d].

3. Final Step:
(a) Iterate over all numbers and find the maximum value in g[x][0], which represents the longest subsequence for all numbers with zero difference.

# Complexity
- Time complexity:
1. Outer Loop:
Iterates over all numbers in nums, so it runs O(n) times.
2. Inner Loops:
The inner loop processes all possible values of y (from 1 to U) and differences d (from U-2 down to 0), taking O(U ^ 2) operations for each number.
3. Total Time Complexity:
O(n⋅ U ^ 2), where n is the length of nums and U=301.

- Space complexity:
O(U ^ 2)

# Code
```python3 []
class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        U = 301
        n = len(nums)
        g = [[0] * U for _ in range(U)]
        for x in nums:
            f = [0] * U
            f[U - 1] = 1  
            for y in range(1, U):
                d = abs(x - y)
                f[d] = max(f[d], g[y][d] + 1)
            g[x][U - 1] = 1
            for d in range(U - 2, -1, -1):
                g[x][d] = max(g[x][d + 1], f[d])
        ans = 0
        for x in range(1, U):
            ans = max(ans, g[x][0])
        return ans
```
['Python3']