[C++, Java] Check for all possible values and there diff - Explained
Intuition
The typical thought on to solve this problem is to start with pick/not-pick type problem where we can pick an item or skip one and at the same time ke
# Intuition
- The typical thought on to solve this problem is to start with pick/not-pick type problem where we can pick an item or skip one and at the same time keep track of the picked item and the last diff so that we can transit to next state with given constraints. 
Here is the code for this intuition :

```
unordered_map<string, int> dp;
int solve(vector<int>& nums, int i, int last, int diff){
    if( i >= nums.size()) return 0;
    string key = to_string(i) + "#" + to_string(last) + "#" + to_string(diff);
    if(dp.find(key) != dp.end()) return dp[key];
    int res = solve(nums, i+1, last, diff);
    if(abs(nums[i] - last) <= diff) res = max(res, 1 + solve(nums, i +1, nums[i], abs(nums[i] - last)));
    return dp[key] = res;
}
int longestSubsequence(vector<int>& nums) {
    return solve(nums, 0, -300, 1000);
}
```
- But here this code will give TLE as the total combintation of the states = 10000 * 300 * 300 = 900000000.

- So need to think about some alternative way rather than classical dp problem.

- Also the smaller possible value of nums[i] that is less than equal to 300 is a good hint on that to start with.

- So to get a solution we can think up to simulate all possible next number and take there possible diff and keep tracking the possible count.
Let Nums = [5, 10, 8, 20, 10, 20]

- To clarify above statement, lets assume we are iterating from the last and lets say we are at a state i = 4, where nums[i] = 10. Now we can check all possible value of next number that we would have picked from the end. It might be possible some numbers we already traversed where as some we have not. Where we have not traversed those values are 0 with all diff where as other those which we have traversed with some diff must have some non zero numbers.

- While checking all possible values, take the diff with respect to the next number and then if we possibly pick that number with that diff then we will add 1 to the next number with the same diff. so for current nums[i] = 10 we might have already visited a number 20 before. And when visited 20, the diff is 10. So we have 20 with 10 diff before set to zero as 20 is the first number( i.e dp[nextNum][diff] = dp[20][10] = 0). Now for 10 when we consider next possible number as 20, as that time we update the dp[nums[i]][diff] = dp[10][10] = dp[nextNum][diff] + 1 = dp[20][10] + 1 = 0 + 1 = 1.
We just not assign it directly, rather we take the max of dp[10][10] and dp[20][10] + 1.

- Now once we done all possible values as the next number, we then collect maximum count possbile for dp[10][diff] where diff will vary from 0 to 300. Here if the lower diff of num have larger count that means we can achive the same with current diff count as well as we are traversing from the end, the diff are gradually increasing towards left of i.
For example, if we have a dp[10][10] = 1 and we have dp[10][9] = 2 then we update the dp[10][10] as 2 as well. 

- While doing so keep tracking the max count possible for all diff with current num.

- Still this is a bit tricky and difficult to think during contest or interview but at the same time good variation of dp problem where we can try to find all possible states before hand. If you still struggling to get the exact crucs of it, try dry run with a smaller input would clarify things more clear.

# Code
```cpp []
int longestSubsequence(vector<int>& nums) {
    int res = 0;
    vector<vector<int>> dp(301, vector<int>(301, 0));
    for(int i = nums.size() - 1; i >= 0; --i){
        for(int nextNum = 1; nextNum <= 300; ++nextNum){
            int diff = abs(nums[i] - nextNum);
            dp[nums[i]][diff] = max(dp[nums[i]][diff] , dp[nextNum][diff] + 1);
        }
        for(int diff = 1; diff < 300; ++diff){
            dp[nums[i]][diff] = max(dp[nums[i]][diff], dp[nums[i]][diff-1]);
            res = max(res, dp[nums[i]][diff]);
        }
    }
    return res;
}
```
```Java []
int longestSubsequence(int[] nums) {
    int res = 0;
    int[][] dp = new int[301][301];
    Arrays.stream(dp).forEach(row -> Arrays.fill(row, 0));
    for(int i = nums.length - 1; i >= 0; --i){
        for(int nextNum = 1; nextNum <= 300; ++nextNum){
            int diff = Math.abs(nums[i] - nextNum);
            dp[nums[i]][diff] = Math.max(dp[nums[i]][diff] , dp[nextNum][diff] + 1);
        }
        for(int diff = 1; diff < 300; ++diff){
            dp[nums[i]][diff] = Math.max(dp[nums[i]][diff], dp[nums[i]][diff-1]);
            res = Math.max(res, dp[nums[i]][diff]);
        }
    }
    return res;
}
```


---

<b>Here is an article of my last interview experience - A Journey to FAANG Company, I recomand you to go through this to know which all resources I have used & how I cracked interview at Amazon:
https://leetcode.com/discuss/interview-experience/3171859/Journey-to-a-FAANG-Company-Amazon-or-SDE2-(L5)-or-Bangalore-or-Oct-2022-Accepted

---


['C++', 'Java']