Dynamic Programming | Longest Subsequence | Beats 100% ✅
IntuitionThe problem can be approached using dynamic programming because it requires finding the longest subsequence under specific constraints. The key observa
## Intuition
The problem can be approached using dynamic programming because it requires finding the longest subsequence under specific constraints. The key observation here is that the range of possible values (from 1 to 300) is small, which allows us to efficiently maintain a dynamic programming (DP) table to compute the solution.

### Key Observations:
- Each number in the subsequence must have a difference of at most 1 with the previous number.
- The range of values is bounded (from 1 to 300), which allows us to efficiently store results in a DP table.

## Approach
1. **DP Table Setup:**
   - We use a 2D DP table `dp[i][j]` where:
     - `i` represents the starting number of the subsequence.
     - `j` represents the maximum allowed difference between consecutive elements.
   
2. **Reverse Iteration:**
   - Start iterating from the end of the array and move backward to the beginning.
   - For each number, update the DP table based on the possible next numbers.
   
3. **Updating the DP Table:**
   - For each possible next number (`next`), calculate the absolute difference with the current number (`difference`).
   - Update `dp[current][difference]` by considering the best subsequence starting from the current number with the given difference.

4. **Track the Global Maximum:**
   - During the iteration, track the global maximum subsequence length and update it when a longer subsequence is found.

## Complexity

- **Time Complexity:**  
  `O(n * k * k)`, where:
  - `n` is the length of the array.
  - `k = 300` (the range of possible values).

- **Space Complexity:**  
  `O(k * k)` for the DP table, where `k = 300`.

# Code
```java []
class Solution {
    public int longestSubsequence(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[301][301]; // DP table to store subsequence lengths
        int maxLength = 1;

        // Traverse the array in reverse order
        for (int i = n - 1; i >= 0; i--) {
            int current = nums[i];
            
            // Update the DP table based on the current number and possible next numbers
            for (int next = 1; next <= 300; next++) {
                int difference = Math.abs(current - next);
                dp[current][difference] = Math.max(dp[current][difference], dp[next][difference] + 1);
            }
            
            // Update the DP table for the current number with all possible differences
            for (int diff = 1; diff <= 300; diff++) {
                dp[current][diff] = Math.max(dp[current][diff], dp[current][diff - 1]);
            }
            
            // Track the maximum subsequence length
            maxLength = Math.max(maxLength, dp[current][300]);
        }

        return maxLength;
    }
}

```
['Array', 'Dynamic Programming', 'Java']