Easy DP | Well explained and commented
Intuition
Notice that the range of numbers is small, so we can exploit this
dp[i][j] is the answer starting with number i with difference atmost j (between this
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- Notice that the range of numbers is small, so we can exploit this
- dp[i][j] is the answer starting with number i with difference atmost j (between this and the next element)
- dp[i][j] is hence max(dp[i][0 to j])
- We update the dp table by starting values of i from the back of our subsequence, so initially, the table is all 0s, then it updates based on the last element and so on...
- So at any point during the update, dp[i][j] is the answer for a subsequence (of the portion of the array already covered from the back) starting with number i with difference j

# Approach
<!-- Describe your approach to solving the problem. -->

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

- Space complexity: O(300*300)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        // Notice that the range of numbers is small, so we can exploit this
        // dp[i][j] is the answer starting with number i with difference atmost j (between this and the next element)
        // dp[i][j] is hence max(dp[i][0 to j])
        // We update the dp table by starting values of i from the back of our subsequence, so initially, the table is all 0s, then it updates based on the last element and so on...
        // So at any point during the update, dp[i][j] is the answer for a subsequence (of the portion of the array already covered from the back) starting with number i with difference j
        int n = nums.size();
        vector<vector<int>> dp(301, vector<int> (301,0)); // initally all 0s
        int ans = 1;
        for(int i=n-1;i>=0;i--){ // iterate from the back
            int num = nums[i];
            for(int j=1;j<=300;j++){ // the next number in the subsequence can be anything from this
                int diff = abs(num - j); // this will be the difference (between ith and next element)
                // The next statement works because dp[i][j] = max(dp[i][0 to j]) which is done in the loop below
                dp[num][diff] = max(dp[num][diff], dp[j][diff] + 1); // The next number can have difference (between it and its next number) as atmost diff, hence we take dp[j][diff]+1
            }
            for(int j=1;j<=300;j++){
                dp[num][j] = max(dp[num][j-1], dp[num][j]); //dp[i][j] = max(dp[i][0 to j])
            }
            ans = max(ans, dp[num][300]); // dp[num][300] is the max among all j in dp[i][j], thus, it is sufficient to take max of all of them
        }
        return ans;
    }
};
```
['Dynamic Programming', 'C++']