C++ | Most Intuitive Explanation | First Go Understanding
ApproachTo solve this problem, we need to find the longest subsequence where the absolute differences between consecutive elements are non-increasing. We can ac
### Approach
To solve this problem, we need to find the longest subsequence where the absolute differences between consecutive elements are non-increasing. We can achieve this using dynamic programming (DP) to track the longest subsequence ending at each number with a specific difference.

### Intuition
DP State Representation:

We use a 2D DP array `dp[num][diff]` where:

`num` is the last element of the subsequence.

`diff` is the last absolute difference between the last two elements of the subsequence.

`dp[num][diff]` stores the length of the longest subsequence ending with num and having the last difference as diff.

### DP Transition:

For each number num in nums, we iterate over all possible previous numbers prev (from 1 to 300).

We calculate the absolute difference diff between num and prev.

We update `dp[num][diff]` by taking the maximum of its `current value` and `1 + dp[prev][diff]`. This ensures we are extending the subsequence ending with prev and having the last difference as diff.

#### Non-Increasing Difference:

After updating `dp[num][diff]`, we ensure the differences are non-increasing by propagating the maximum value from higher differences to lower differences. This is done by iterating from the highest difference (299) down to 0 and updating `dp[num][j]` to be the maximum of `dp[num][j]` and `dp[num][j+1]`.

### Result:

The answer is the maximum value found in the DP array after processing all numbers.

### Algorithm
* Initialize a 2D DP array dp of size 301 x 301 with all values set to 0.

* Iterate over each number num in nums.

* For each num, iterate over all possible previous numbers prev from 1 to 300.

* Calculate the absolute difference diff between num and prev.

* Update `dp[num][diff]` to be the maximum of its current value and 1 + `dp[prev][diff]`.

* After updating `dp[num][diff]`, iterate from the highest difference (299) down to 0 and update `dp[num][j]` to be the maximum of `dp[num][j]` and `dp[num][j+1]`.

* Keep track of the maximum value in the DP array as the result.

### Complexity Analysis
#### Time Complexity: O(n * 300)

We iterate over each number in nums (n numbers) and for each number, we iterate over all possible previous numbers (300 iterations). Additionally, we perform a backward pass over the differences (300 iterations). Thus, the overall time complexity is O(n * 300).

#### Space Complexity: O(301 * 301)

We use a 2D DP array of size 301 x 301, which results in a space complexity of O(301 * 301).

# Code
```cpp []
class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(301, vector<int>(301));
        int ans = 0;

        for(int i = 0 ; i < n; i++){
            int num = nums[i];

            for(int prev = 1; prev <= 300; prev++){
                int diff = abs(prev - num);
                dp[num][diff] = max(dp[num][diff], 1 + dp[prev][diff]);
            }

            for(int j = 299; j >=0 ; j--){
                dp[num][j] = max(dp[num][j], dp[num][j+1]);
                ans = max(ans, dp[num][j]);
            }
        }

        return ans;
    }
};
```
['Dynamic Programming', 'C++']