# Longest Subsequence with Limited Difference DP SOLUTION , in CP format 
IntuitionThe problem involves finding the length of the longest subsequence in the array such that the difference between any two consecutive elements is at mos
### Intuition

The problem involves finding the length of the longest subsequence in the array such that the difference between any two consecutive elements is at most `k`. To solve this, we will use dynamic programming (DP) to track the longest subsequences ending at each number and with various differences between adjacent numbers.

### Approach

1. **Initial Setup**: We calculate the maximum possible difference (`max_diff`) between any two numbers in the array. This is because the subsequence differences must lie within the range from 0 to `max_diff`.
2. **Dynamic Programming Table**: We create a DP table `dp`, where `dp[x][d]` holds the length of the longest subsequence ending at value `x` with difference `d` between consecutive elements.
3. **Iterate from Right to Left**: We process the array from right to left. For each element, we consider all possible differences `d` from 0 to `max_diff` and update the DP table based on whether a subsequence can be formed by adding this element to any subsequences with previous differences.
4. **Update Result**: The final result will be the maximum value in the DP table, representing the longest subsequence length found.

### Complexity

- **Time Complexity**: The time complexity is \(O(n \times M)\), where \(n\) is the number of elements in the input array, and \(M\) is the maximum difference between the largest and smallest values in the array.
- **Space Complexity**: The space complexity is \(O(n \times M)\), as we are storing a DP table of size \(n \times M\).

### Code

# Code
```c++ []
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

#define SIZE(x) ((x).size())
#define IF_EMPTY_RETURN_ZERO(x) if (SIZE(x) == 0) return 0;

class Solution {
public:
    int longestSubsequence(std::vector<int>& nums) {
        IF_EMPTY_RETURN_ZERO(nums);
        
        int n = SIZE(nums);
        std::vector<std::vector<int>> dp(301, std::vector<int>(301, 0));
        std::vector<bool> check(301, false);
        
        check[nums.back()] = true;
        int ans = 0;
        for (int i = n - 2; i >= 0; i--) {
            int Max = 0;
            std::vector<int> vt(301, 0);
            
            for (int k = 0; k <= 300; k++) {
                if (nums[i] + k <= 300 && check[nums[i] + k]) {
                    vt[k] = std::max(vt[k], dp[nums[i] + k][k] + 1);
                }
                if (nums[i] - k >= 0 && check[nums[i] - k]) {
                    vt[k] = std::max(vt[k], dp[nums[i] - k][k] + 1);
                }
                if (k - 1 >= 0) {
                    vt[k] = std::max(vt[k], vt[k - 1]);
                }
            }

            for (int k = 0; k <= 300; k++) {
                dp[nums[i]][k] = std::max(dp[nums[i]][k], vt[k]);
                ans = std::max(ans, dp[nums[i]][k]);
            }


            check[nums[i]] = true;
        }

        return ans + 1;
    }
};
```
['C++']