Beginner friendly DP with prefix/suffix operations
Intuitionfirstly I couldn't solve it on my own but i think sharing the idea with logic will help others as well as me to understand it wellApproachBasically,I c
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
firstly I couldn't solve it on my own but i think sharing the idea with logic will help others as well as me to understand it well
# Approach
<!-- Describe your approach to solving the problem. -->
Basically,I created a dp vector in which dp[i][j] is the max. lenght of subsequence ending at index i(we are picking element at index i) with last difference j (means the last diff used to make that subsequence).
Since in dp[i][j] we are picking the ith element nums[i], we must have picked either nums[i]-j or nums[i]+j or both , previous to ith element.
here comes our occurence vector occ. , occ[i][j] represent the first occurence of j(a number between 0 and 300) before i, which will give me the index of nums[i]-j(lower) or nums[i]+j(higher).
 int x = occ[i][lower];
found index if its not -1 which mean it actually occurs
 dp[i][j]=1+max(dp[x][j],dp[x][j+1],dp[x][j+2].....,dp[x][300]);
similarily we can do for higher,
 int y= occ[i] [higher];
dp[i][j]=1+max(dp[y][j],dp[y][j+1],dp[y][j+2].....,dp[y][300]);

Now the tough part comes,
we can observe a pattern that we are taking max of all possible difference with value j or more.
here comes our suff vector (sorry name should be suff) 
suff[i][j]=>max len of subsequence ending at i and diff is j or more 
hence we can write dp[i][j]=1+ suff[x][j];
                   dp[i][j]=max(dp[i][j],1+suff[i][j]);
but we need to update the suff vector also right?
so when we calculated dp[i][j] and if we are iterating j from 300 to 0
on every iteration of the inner loop j decreases by one 
and we get dp[i][j--], and now suff[i][j--] = max(suff[i][j--],suff[i][j]).
hence I maintained a variable d which stores maximum value on every iteration of j and hence we can say suff[i][j]=d at the end of every iteration of inner loop.

                   



# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
o(n*|nums[i]|)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(n*|nums[i]|)
# Code
```cpp []
class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(301, 1));  // dp[i][j]: max length ending at i with diff j
        vector<vector<int>> occ(n, vector<int>(301, -1));  // occ[i][j]: first occurrence of j before i
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= 300; j++) {
                occ[i][j] = occ[i - 1][j];  
            }
            occ[i][nums[i-1]] = i-1;  
        }
        vector<vector<int>> suff(n,vector<int>(300+1,1));
        //suff[i][j]->max len of subsequence ending at index i s.t.   the last diff is j or more
        for (int i = 0; i < n; i++) {
            int d=0;
            for (int j = 300; j>=0; j--) {
                int lower = nums[i] - j;
                if (lower >= 0 && occ[i][lower] != -1) {
                    int x = occ[i][lower];
                    dp[i][j]=1+suff[x][j];
                }
                d=max(d,dp[i][j]);
                
                int higher = nums[i] + j;
                if (higher <= 300 && occ[i][higher] != -1) {
                    int x = occ[i][higher];
                    dp[i][j]=max(dp[i][j],1+suff[x][j]);
                }
                d=max(d,dp[i][j]);
                suff[i][j]=d;
            }
        }
        int ans = 0;
        for (int i=0;i<n;i++) {
            for (int j=0;j<=300;j++) {
                ans = max(ans,dp[i][j]);
            }
        }
        return ans;
    }
};

```

['C++']