# Longest Subsequence With Decreasing Adjacent Difference
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-subsequence-with-decreasing-adjacent-difference)
Canonical: https://scaleengineer.com/dsa/problems/longest-subsequence-with-decreasing-adjacent-difference
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Juspay](https://scaleengineer.com/companies/juspay)
---
## Problem
You are given an array of integers `nums`.

Your task is to find the length of the **longest** subsequence `seq` of `nums`, such that the **absolute differences** between _consecutive_ elements form a **non-increasing sequence** of integers. In other words, for a subsequence `seq0`, `seq1`, `seq2`, ..., `seqm` of `nums`, `|seq1 - seq0| >= |seq2 - seq1| >= ... >= |seqm - seqm - 1|`.

Return the length of such a subsequence.

**Example 1:**

**Input:** nums = \[16,6,3\]

**Output:** 3

**Explanation:** 

The longest subsequence is `[16, 6, 3]` with the absolute adjacent differences `[10, 3]`.

**Example 2:**

**Input:** nums = \[6,5,3,4,2,1\]

**Output:** 4

**Explanation:**

The longest subsequence is `[6, 4, 2, 1]` with the absolute adjacent differences `[2, 2, 1]`.

**Example 3:**

**Input:** nums = \[10,20,10,19,10,20\]

**Output:** 5

**Explanation:** 

The longest subsequence is `[10, 20, 10, 19, 10]` with the absolute adjacent differences `[10, 10, 9, 9]`.

**Constraints:**

* `2 <= nums.length <= 104`
* `1 <= nums[i] <= 300`

# Approaches
## Dynamic Programming with Value-Based State
This approach uses dynamic programming where the state is based on the values of the numbers rather than their indices, which is suitable given the constraint on the values (`<= 300`). We define a DP state `dp[v][d]` to be the length of the longest valid subsequence ending with value `v` and whose last two elements have an absolute difference of `d`.

We iterate through each number `num` in the input array. For each `num`, we consider it as the new end of a subsequence. We then iterate through all possible values `prev_v` that could have preceded `num` in a subsequence. To extend a subsequence ending at `prev_v`, the new difference `d = |num - prev_v|` must be less than or equal to the previous difference `prev_d`. This requires searching for the best `prev_d` for each `(num, prev_v)` pair, leading to a nested loop structure.
**Time:** O(N * V_max * D_max), where `N` is the length of `nums`, `V_max` is the maximum value, and `D_max` is the maximum difference. With `N=10^4` and `V_max, D_max` around 300, this is roughly `10^4 * 300 * 300 = 9 * 10^8`, which is too slow. · **Space:** O(V_max * D_max), where `V_max` is the maximum possible value in `nums` (300) and `D_max` is the maximum possible difference (299). This is approximately O(300*300), which is feasible.
**Pros:** The DP state correctly captures the problem's subproblems.; It provides a structural foundation for the more efficient solution.
**Cons:** The time complexity is too high for the given constraints and will likely result in a Time Limit Exceeded (TLE) error.
### Explanation
The core of this method is a 2D DP table, `dp[v][d]`, which stores the length of the longest valid subsequence ending with value `v` and a final difference of `d`. We also use an auxiliary array, `maxLen[v]`, to keep track of the maximum length of any subsequence ending in `v`, which helps us know if `v` has appeared in `nums` so far.

We process the input array `nums` one element at a time. For each `num`, we try to form a new, longer subsequence by appending `num` to existing valid subsequences. We iterate through all possible previous values `prev_v` (from 1 to 300). If `prev_v` has been seen before (i.e., `maxLen[prev_v] > 0`), we calculate the new difference `d = |num - prev_v|`. We then perform a search within `dp[prev_v]` to find the longest subsequence we can extend, which is one whose last difference `prev_d` is at least `d`. This search is a linear scan, contributing to the high time complexity. After calculating the potential new lengths for all `prev_v`, we update the DP table for `num`.

```java
class Solution {
    public int longestSubsequence(int[] nums) {
        int V_MAX = 300;
        int D_MAX = 300;

        // dp[v][d]: length of the longest valid subsequence ending with value v and last difference d
        int[][] dp = new int[V_MAX + 1][D_MAX];
        // maxLen[v]: max length of any valid subsequence ending with value v
        int[] maxLen = new int[V_MAX + 1];
        
        int ans = 1;

        for (int num : nums) {
            int[] newDpRowForNum = new int[D_MAX];
            int newMaxLenForNum = 1;

            for (int prev_v = 1; prev_v <= V_MAX; prev_v++) {
                if (maxLen[prev_v] > 0) { // if prev_v has been seen before
                    int d = Math.abs(num - prev_v);
                    
                    // Find max length of subsequence ending at prev_v with last diff >= d
                    int lenToExtend = 0;
                    for (int prev_d = d; prev_d < D_MAX; prev_d++) {
                        lenToExtend = Math.max(lenToExtend, dp[prev_v][prev_d]);
                    }
                    
                    int newLen = (lenToExtend == 0) ? 2 : lenToExtend + 1;
                    
                    newDpRowForNum[d] = Math.max(newDpRowForNum[d], newLen);
                    newMaxLenForNum = Math.max(newMaxLenForNum, newLen);
                }
            }

            for (int d = 0; d < D_MAX; d++) {
                dp[num][d] = Math.max(dp[num][d], newDpRowForNum[d]);
            }
            
            maxLen[num] = Math.max(maxLen[num], newMaxLenForNum);
            if (maxLen[num] == 0) {
                maxLen[num] = 1;
            }
            
            ans = Math.max(ans, maxLen[num]);
        }

        return ans;
    }
}
```
### Algorithm
1. Define a 2D DP table `dp[v][d]`, where `dp[v][d]` stores the length of the longest valid subsequence ending with the value `v` and having a last absolute difference of `d`.
2. Define an auxiliary array `maxLen[v]` to store the maximum length of any valid subsequence ending with value `v`. This helps to quickly check if a value has been encountered before.
3. Initialize `dp` and `maxLen` tables with 0. The answer `ans` is initialized to 1 (for single-element subsequences).
4. Iterate through each number `num` in the input array `nums`.
5. For each `num`, iterate through all possible previous values `prev_v` from 1 to 300.
6. If `maxLen[prev_v] > 0`, it means `prev_v` has been seen. We can potentially extend a subsequence ending at `prev_v` with `num`.
7. Calculate the new difference `d = |num - prev_v|`.
8. To satisfy the non-increasing difference condition, the previous difference `prev_d` must be greater than or equal to `d`. We find the maximum length of a subsequence ending at `prev_v` that meets this condition by iterating from `d` to the maximum possible difference. `len_to_extend = max(dp[prev_v][k])` for `k >= d`.
9. The new subsequence length will be `len_to_extend + 1`. If no such subsequence exists (`len_to_extend == 0`), we can still form a new subsequence of length 2, `[prev_v, num]`.
10. Update a temporary DP row for `num` with the calculated new length.
11. After checking all possible `prev_v`, merge the temporary row into the main `dp[num]` row and update `maxLen[num]` and the overall `ans`.

## Optimized Dynamic Programming with Suffix Maximums
This approach significantly optimizes the previous DP solution by addressing its main bottleneck: the repeated linear scan to find the best subsequence to extend. The scan `max(dp[prev_v][k])` for `k >= d` is a range maximum query. We can answer these queries in O(1) time by pre-calculating suffix maximums for each row of our DP table.

We introduce a new table, `suffixMaxDp[v][d]`, to store these suffix maximums. When processing a new number `num` from the input, we can use this table to instantly find the best valid subsequence ending at any `prev_v` to extend. After we compute and update the DP values for `num`, we only need to update the single corresponding row `suffixMaxDp[num]`. This reduces the complexity within the main loop from O(M^2) to O(M), making the overall algorithm efficient enough to pass the given constraints.
**Time:** O(N * (V_max + D_max)). For each of the `N` numbers, we iterate through `V_max` possible previous values with O(1) lookups, and then perform updates that take O(D_max) time. This simplifies to O(N * M) where `M` is ~300. With `N=10^4`, this is roughly `10^4 * 300 = 3 * 10^6` operations, which is well within typical time limits. · **Space:** O(V_max * D_max), same as the unoptimized approach. We need three tables of this approximate size. With `V_max=300, D_max=299`, this is feasible.
**Pros:** Highly efficient time complexity that meets the problem constraints.; Effectively solves the problem by optimizing the query for valid previous subsequences.
**Cons:** The implementation is more complex, requiring careful management of three separate data structures.; The space complexity remains the same as the unoptimized approach.
### Explanation
We build upon the previous DP approach. The state `dp[v][d]` and helper array `maxLen[v]` remain the same. The key addition is the `suffixMaxDp[v][d]` table, which is maintained throughout the process. For each `num` in the input array, we calculate the potential new lengths of subsequences ending in `num`.

For each possible previous value `prev_v`, we determine the new difference `d = |num - prev_v|`. Instead of a loop, we directly query `suffixMaxDp[prev_v][d]` to find the length of the longest subsequence ending in `prev_v` with a last difference of at least `d`. This is an O(1) lookup. Based on this, we calculate the new length and store it temporarily.

After considering all possible `prev_v`, we update the `dp[num]` row with the new values. A crucial step follows: if the `dp[num]` row has changed, we must re-calculate the `suffixMaxDp[num]` row to ensure it's correct for subsequent iterations. This update takes O(D_max) time. This optimization brings the total time complexity down to a feasible level.

```java
class Solution {
    public int longestSubsequence(int[] nums) {
        int V_MAX = 300;
        int D_MAX = 300;

        int[][] dp = new int[V_MAX + 1][D_MAX];
        int[] maxLen = new int[V_MAX + 1];
        int[][] suffixMaxDp = new int[V_MAX + 1][D_MAX];

        int ans = 1;

        for (int num : nums) {
            int[] newDpRowForNum = new int[D_MAX];
            int newMaxLenForNum = 1;

            for (int prev_v = 1; prev_v <= V_MAX; prev_v++) {
                if (maxLen[prev_v] > 0) {
                    int d = Math.abs(num - prev_v);
                    int lenToExtend = suffixMaxDp[prev_v][d];
                    int newLen = (lenToExtend == 0) ? 2 : lenToExtend + 1;
                    newDpRowForNum[d] = Math.max(newDpRowForNum[d], newLen);
                    newMaxLenForNum = Math.max(newMaxLenForNum, newLen);
                }
            }

            boolean updated = false;
            for (int d = 0; d < D_MAX; d++) {
                if (newDpRowForNum[d] > dp[num][d]) {
                    dp[num][d] = newDpRowForNum[d];
                    updated = true;
                }
            }
            
            maxLen[num] = Math.max(maxLen[num], newMaxLenForNum);
            if (maxLen[num] == 0) maxLen[num] = 1;

            if (updated) {
                int suffixMax = 0;
                for (int d = D_MAX - 1; d >= 0; d--) {
                    suffixMax = Math.max(suffixMax, dp[num][d]);
                    suffixMaxDp[num][d] = suffixMax;
                }
            }
            
            ans = Math.max(ans, maxLen[num]);
        }

        return ans;
    }
}
```
### Algorithm
1. Use the same DP state `dp[v][d]` and `maxLen[v]` as the previous approach.
2. Introduce a new auxiliary table, `suffixMaxDp[v][d]`, which stores the suffix maximum of each row in the `dp` table. Specifically, `suffixMaxDp[v][d] = max(dp[v][k])` for all `k >= d`.
3. Initialize all tables to 0 and `ans` to 1.
4. Iterate through each `num` in `nums`.
5. For each `num`, iterate through all possible previous values `prev_v`.
6. If `prev_v` has been seen (`maxLen[prev_v] > 0`), calculate the new difference `d = |num - prev_v|`.
7. The crucial optimization: instead of looping to find the best previous subsequence to extend, we can get this information in O(1) time from our precomputed suffix maximum table: `len_to_extend = suffixMaxDp[prev_v][d]`.
8. Calculate the new length (`2` if `len_to_extend` is 0, otherwise `len_to_extend + 1`) and update a temporary DP row for `num`.
9. After checking all `prev_v`, update the main `dp[num]` table.
10. If `dp[num]` was modified, the corresponding `suffixMaxDp[num]` row must be recomputed. This takes O(D_max) time.
11. Update `maxLen[num]` and the overall `ans`.