Detailed explained dp approach -> tabulation [C++/Java/Python/Javascript] || Beats 100%
ApproachDynamic Programming (DP):
dp[num][diff] represents the length of the longest subsequence that ends at number num with a fixed difference diff between co
# Approach
# Dynamic Programming (DP):

1. dp[num][diff] represents the length of the longest subsequence that ends at number num with a fixed difference diff between consecutive elements.
# Suff array (Suffix Maximums):

1. suff[num][diff] stores the maximum length of subsequences ending at num with differences greater than or equal to diff. It helps optimize the lookup when updating dp.
# Goal:

1. Find the longest subsequence such that for every pair of adjacent elements in the subsequence, the absolute difference is constant (or has been chosen from the range).

# Step-by-Step Logic
# Initialization:
1. Create two 2D arrays:

2. dp[301][301]: Initialized to 0. Stores the longest subsequence ending with a given number and a specific difference.
3. suff[301][301]: Initialized to 0. Maintains suffix maximums for optimization.
4. ans: Keeps track of the overall maximum subsequence length. Initially set to 1.

# Iterating Through nums:
 For each number num in nums:

# Initialize Base Case:

1.  If dp[num][0] is less than 1, set it to 1. This ensures that any number can start its own subsequence of length 1.
2. Update dp[num][diff]:

3.  Iterate over all possible preceding numbers preNum (from 1 to 300).
Calculate the absolute difference, diff = |num - preNum|.
4.  For each diff, determine the best previous subsequence that can be extended:

# Case 1: bestNum > 0:

1. If there is a valid subsequence ending at preNum with difference diff (bestNum = suff[preNum][diff]), 
2. extend it:dp[num][diff]=max(dp[num][diff],bestNum+1)
# Case 2: Default case:

1. If no valid subsequence with diff exists but there is at least one valid subsequence starting with preNum:dp[num][diff]=max(dp[num][diff],2)
2. This initializes a subsequence of length 2 (just preNum and num).

3. Update the global maximum:ans=max(ans,dp[num][diff])
#  Update suff Array:
1. After processing all differences for the current num, update suff[num][diff] to store the maximum subsequence lengths for num for all differences:
2. Start from the largest possible difference (d = 299) and move downward:suff[num][d]=max(suff[num][d+1],dp[num][d])
3. This ensures suff[num][d] contains the best subsequence length for num with differences ≥ d.
# Final Return:
After iterating through all numbers in nums, return the value of ans, which holds the length of the longest subsequence.
# Complexity
- Time complexity:
O(N* 300*300)

- Space complexity:
O(300*300)

# Code
```cpp []
class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        vector<vector<int>> dp(301, vector<int>(301));
        vector<vector<int>> suff(301, vector<int>(301));

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

            for (int pre_num = 1; pre_num <= 300; pre_num++) {
                int diff = abs(num - pre_num);

                int new_num = suff[pre_num][diff];

                if (new_num > 0) {
                    dp[num][diff] = max(dp[num][diff], new_num + 1);
                } else {
                    if (suff[pre_num][0] > 0) {
                        dp[num][diff] = max(dp[num][diff], 2);
                    }
                }
                ans = max(ans, dp[num][diff]);
            }

            suff[num][299] = dp[num][299];

            for (int i = 298; i >= 0; i--) {
                suff[num][i] = max(suff[num][i + 1], dp[num][i]);
            }
        }

        return ans;
    }
};

```
```java []
class Solution {
    public int longestSubsequence(int[] nums) {
        int[][] dp = new int[301][301];
        int[][] suff = new int[301][301];

        int ans = 1;

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

            for (int preNum = 1; preNum <= 300; preNum++) {
                int diff = Math.abs(num - preNum);

                int newNum = suff[preNum][diff];

                if (newNum > 0) {
                    dp[num][diff] = Math.max(dp[num][diff], newNum + 1);
                } else {
                    if (suff[preNum][0] > 0) {
                        dp[num][diff] = Math.max(dp[num][diff], 2);
                    }
                }

                ans = Math.max(ans, dp[num][diff]);
            }

            suff[num][299] = dp[num][299];

            for (int i = 298; i >= 0; i--) {
                suff[num][i] = Math.max(suff[num][i + 1], dp[num][i]);
            }
        }

        return ans;
    }
}

```
```python []
class Solution:
    def longestSubsequence(self, nums):
        dp = [[0] * 301 for _ in range(301)]
        suff = [[0] * 301 for _ in range(301)]

        ans = 1

        for num in nums:
            if dp[num][0] < 1:
                dp[num][0] = 1

            for pre_num in range(1, 301):
                diff = abs(num - pre_num)

                new_num = suff[pre_num][diff]

                if new_num > 0:
                    dp[num][diff] = max(dp[num][diff], new_num + 1)
                else:
                    if suff[pre_num][0] > 0:
                        dp[num][diff] = max(dp[num][diff], 2)

                ans = max(ans, dp[num][diff])

            suff[num][299] = dp[num][299]

            for i in range(298, -1, -1):
                suff[num][i] = max(suff[num][i + 1], dp[num][i])

        return ans

```
```Javascript []
class Solution {
    longestSubsequence(nums) {
        let dp = Array.from({ length: 301 }, () => Array(301).fill(0));
        let suff = Array.from({ length: 301 }, () => Array(301).fill(0));

        let ans = 1;

        for (let num of nums) {
            if (dp[num][0] < 1) {
                dp[num][0] = 1;
            }

            for (let preNum = 1; preNum <= 300; preNum++) {
                let diff = Math.abs(num - preNum);

                let newNum = suff[preNum][diff];

                if (newNum > 0) {
                    dp[num][diff] = Math.max(dp[num][diff], newNum + 1);
                } else {
                    if (suff[preNum][0] > 0) {
                        dp[num][diff] = Math.max(dp[num][diff], 2);
                    }
                }

                ans = Math.max(ans, dp[num][diff]);
            }

            suff[num][299] = dp[num][299];

            for (let i = 298; i >= 0; i--) {
                suff[num][i] = Math.max(suff[num][i + 1], dp[num][i]);
            }
        }

        return ans;
    }
}

```

['Array', 'Math', 'Dynamic Programming', 'Greedy', 'Recursion', 'Memoization', 'Python', 'C++', 'Java', 'JavaScript']