🚀 0ms | Beats 100% Submissions | Dynamic Programming Solution
Intuition
The problem can be approached using dynamic programming because it involves finding the longest subsequence under specific constraints.
The key observ
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
1. The problem can be approached using dynamic programming because it involves finding the longest subsequence under specific constraints.
2. The key observation is that the range of numbers is small, allowing us to maintain a DP table for efficient computation.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Use a 2D DP table dp[i][j], where:
* i represents the starting number of the subsequence.
* j represents the maximum allowed difference between consecutive elements.
2. Iterate from the end of the array to the beginning, updating the DP table based on the current number and possible next numbers.
3. Update dp[i][j] by considering the best subsequence starting from the current number with a given difference.
4. Track the global maximum subsequence length during the updates.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
* O(n×k×k), where 𝑛 is the length of the array and k is the range of possible values (300 in this case).

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
* O(k×k) for the DP table.

# Code
```cpp []
class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(301, vector<int>(301, 0));
        int maxLength = 1;

        for (int i = n - 1; i >= 0; i--) {
            int current = nums[i];
            for (int next = 1; next <= 300; next++) {
                int difference = abs(current - next);
                dp[current][difference] = max(dp[current][difference], dp[next][difference] + 1);
            }
            for (int diff = 1; diff <= 300; diff++) {
                dp[current][diff] = max(dp[current][diff], dp[current][diff - 1]);
            }
            maxLength = max(maxLength, dp[current][300]);
        }

        return maxLength;
    }
};

```
['Array', 'Dynamic Programming', 'Recursion', 'C++']