Java Dynamic Programming Beats 100%
ApproachStore the length of the longest possibel subsequence in an 2D dp array.
The coordinates encode what the last number of the sequence was and the maximum
# Approach
Store the length of the longest possibel subsequence in an 2D dp array. 
The coordinates encode what the last number of the sequence was and the maximum of the absolute difference to the next number. 

# Complexity
n := nums.length
k := maximum number in the array (mostly 300)
- Time complexity:
O(k*n)

- Space complexity:
O(k²)

# Code
```java []
class Solution {
    public int longestSubsequence(int[] nums) {
        int max = 1;
        for (int value : nums) max = Math.max(max, value);
        int[][] dp = new int[max+1][max];
        for (int num : nums) {
            int thisMax = 1;
            for (int i = max-1; i >= 0; i--) {
                if (num - i > 0 && dp[num - i][i] >= thisMax) thisMax = dp[num - i][i] + 1;
                if (num + i < max+1 && dp[num + i][i] >= thisMax) thisMax = dp[num + i][i] + 1;
                dp[num][i] = thisMax;
            }
        }
        max = 0;
        for (int[] row : dp) max = Math.max(max, row[0]);
        return max;
    }
}
```
['Java']