Notes for myself || Tabulation || Suffix max
Intuition
Now first when i saw this problem i thought of using 3 variables in the dp state ie the curr Index, prev Number, and the prev diff. This would be of t
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- Now first when i saw this problem i thought of using 3 variables in the dp state ie the curr Index, prev Number, and the prev diff. This would be of time Comp $$O(n*300*300)$$ which would give me TLE as the expected time comp was around n^2
- So we know one thing for sure. We need to minimize the dp states from 3 to 2, but what do we eliminate
- We ofc need the current index as we need to iterate through all possible values 
- Now do we need the prev number ? yes
- Now do we need the previous difference ? No and I will explain in detail why
- We know that for a given index, we would have computed the longest subsequence length upto that index correct ? Can I say instead of having that prev diff state variable, I will just go to all possible numbers in the array whose diff along with prev num is greater than the current diff
- ie current diff = abs(currentNum - prevNum) // This we get from the 2 dp states
- previous diff => Loop through all the previous numbers and compute the diff with the prevNum. If that prev diff is greater than the current diff, then and only then we can include the current num in our subsequence correct ? Think properly 
- So technically out of all those subsequences, we will take the maximum length of all those subsequences, and add 1 to them ie adding the current number

# Shock factor
- Now even if we do the above approach, we will get a TLE coz there are 2 dp states both of them contribute 300*300, and we iterate through all possible numbers which will add more complexity, ie giving us TLE
- Our question is, is there a way to do that operation in Constant time comp
- Lets revise ? What is the operation? Given the number and the difference, we need to find the maximum subsequence length ending at that number where the differences of all elements in that subsequence is greater than the given difference. (complicated right, it took me 5 days to understand so take it all in slowly)
- We will use suffix max approach here, where suffix max stores 2 states itself, the number and the difference
- Why suffix max ? why not prefix max ? We are giving the difference variable in the suffix max state right ? That indicates what, it says we need to find the largest subsequence where every difference in that subsequence is greater than the given difference
- If i have a subsequence where each and every difference between adjacent elements is greater than a value called "diff", can i say for sure that it will be greater than a value "diff-1" or any value less than diff ? YES na
- That is the entire logic, i blew my brains our trying to understand it, and i know i dont understand it well yet. gonna come back to this again for sure
- 

# Complexity
- Time complexity: $$O(n * 300)$$
<!-- 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) {
        vector<vector<int>> dp(301, vector<int> (301)); // stores [currNum][currDiff]
        vector<vector<int>> suffixMax(301, vector<int> (301)); // stores [endNum][diff]

        int ans = 1;
        for(auto num :  nums){
            if(dp[num][0] < 1){
                dp[num][0] = 1;
            }

            for(int prevNum = 1; prevNum <= 300; prevNum++){
                int dNew = abs(prevNum - num);
                int maxlen = suffixMax[prevNum][dNew];

                if(maxlen > 0){
                    dp[num][dNew] = max(dp[num][dNew], maxlen + 1);
                } else{
                    if(suffixMax[prevNum][0] > 0){
                        dp[num][dNew] = max(dp[num][dNew], 2);
                    }
                }
                ans = max(ans, dp[num][dNew]);
            }

            suffixMax[num][299] = dp[num][299];
            for(int diff = 298; diff>=0; diff--){
                suffixMax[num][diff] = max(suffixMax[num][diff+1], dp[num][diff]);
            }
        }
        return ans;
    }
};
```
['C++']