[JAVA] Beats 100% Solution | with Simple Generic Intution
IntuitionRange of numbers only being upto 300, limits the possibility of maximum difference between two numbers to be less than equal to 299.
This gives some in
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Range of numbers only being upto `300`, limits the possibility of maximum difference between two numbers to be less than equal to `299`. 
This gives some intution that we should be iterating over the absolute difference for each index probably. 
And constraints are of range 10^4 and 300, so it gives some idea that this can be solved with 2 dimentional DP.

# Approach
<!-- Describe your approach to solving the problem. -->
We create our `dp[idx][diff]`, which stores the length of maximum length subsequece upto index = idx, and difference >= diff.

now we can come to this state dp[idx][diff] from any previous index in the array. so it will be `dp[0][], dp[1][].... dp[idx][]`

But, the condition it must satisfy is that for each previous index we can come from, we will only come when it's difference is more than or equal to current diff.
So, for `dp[idx][diff]`, we can come from 
max { 
     `dp[0][0], dp[0][1]....dp[0][diff]` ,
     `dp[1][0], dp[1][1]....d[1][diff]` ,
     .
     .
     `dp[idx][0], dp[idx][1]....dp[idx][diff]`
}

but time complexity for this will be O(n * 300 * 300), which will give TLE
To optimise this, I have done a simple thing in the code, try finding it your self, once you understand the approach :)

Hint:```if(difference != 299) dp[indx][difference] = dp[indx][difference + 1];```
It is this line of code. This help us keep the time complexity O(n * 300). How? Why?

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

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

# Code
```java []
class Solution {
    public int longestSubsequence(int[] nums) {
        int[][] dp = new int[nums.length][300];
        for(int[] arr : dp) Arrays.fill(arr, 1);

        int[] mp = new int[301];
        Arrays.fill(mp, -1);
        mp[nums[0]] = 0;
        int ans = 1;

        for(int indx = 1; indx < nums.length; indx++) { // 10^4
            for(int difference = 299; difference >= 0; difference--) { // 300
                if(difference != 299) dp[indx][difference] = dp[indx][difference + 1];

                int k = nums[indx] - difference;
                if(k >= 1 && k <= 300 && mp[k] != -1) {
                    int kLastIndx = mp[k];
                    dp[indx][difference] = Math.max(dp[indx][difference], dp[kLastIndx][difference] + 1);
                }

                k = nums[indx] + difference;
                if(k >= 1 && k <= 300 && mp[k] != -1) {
                    int kLastIndx = mp[k];
                    dp[indx][difference] = Math.max(dp[indx][difference], dp[kLastIndx][difference] + 1);
                }
                
                ans = Math.max(ans, dp[indx][difference]);
            }
            
            mp[nums[indx]] = indx;
        }

        return ans;
    }
};
```
['Java']