Longest Subsequence With Decreasing Adjacent Difference

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.

Examples

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 <= 10^4
• 1 <= nums[i] <= 300

Solution

Method 1 – Dynamic Programming with State Tracking

Intuition

We want the longest subsequence where the absolute differences between consecutive elements form a non-increasing sequence. For each pair, we can try to extend a previous valid subsequence if the new difference is not greater than the last one.

Approach

1. Use a DP array where dp[i][d] is the length of the longest subsequence ending at index i with last difference d.
2. For each pair (i, j) with j < i, compute diff = abs(nums[i] - nums[j]).
3. For each possible previous difference prev_d >= diff, try to extend the subsequence.
4. Track the maximum length found.
5. Optimize by using a map to store only relevant differences for each index.

Code

C++

class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int n = nums.size(), ans = 1;
        vector<unordered_map<int, int>> dp(n);
        for (int i = 0; i < n; ++i) {
            dp[i][0] = 1;
            for (int j = 0; j < i; ++j) {
                int d = abs(nums[i] - nums[j]);
                for (auto& [prev_d, l] : dp[j]) {
                    if (prev_d >= d) {
                        dp[i][d] = max(dp[i][d], l + 1);
                        ans = max(ans, dp[i][d]);
                    }
                }
            }
        }
        return ans;
    }
};

Go

func longestSubsequence(nums []int) int {
    n, ans := len(nums), 1
    dp := make([]map[int]int, n)
    for i := range dp {
        dp[i] = map[int]int{0: 1}
    }
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            d := abs(nums[i] - nums[j])
            for prevD, l := range dp[j] {
                if prevD >= d {
                    if dp[i][d] < l+1 {
                        dp[i][d] = l + 1
                    }
                    if ans < dp[i][d] {
                        ans = dp[i][d]
                    }
                }
            }
        }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }

Java

class Solution {
    public int longestSubsequence(int[] nums) {
        int n = nums.length, ans = 1;
        Map<Integer, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) dp[i] = new HashMap<>();
        for (int i = 0; i < n; i++) {
            dp[i].put(0, 1);
            for (int j = 0; j < i; j++) {
                int d = Math.abs(nums[i] - nums[j]);
                for (int prevD : dp[j].keySet()) {
                    if (prevD >= d) {
                        int l = dp[j].get(prevD) + 1;
                        dp[i].put(d, Math.max(dp[i].getOrDefault(d, 0), l));
                        ans = Math.max(ans, dp[i].get(d));
                    }
                }
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun longestSubsequence(nums: IntArray): Int {
        val n = nums.size
        var ans = 1
        val dp = Array(n) { mutableMapOf(0 to 1) }
        for (i in 0 until n) {
            for (j in 0 until i) {
                val d = kotlin.math.abs(nums[i] - nums[j])
                for ((prevD, l) in dp[j]) {
                    if (prevD >= d) {
                        dp[i][d] = maxOf(dp[i].getOrDefault(d, 0), l + 1)
                        ans = maxOf(ans, dp[i][d]!!)
                    }
                }
            }
        }
        return ans
    }
}

Python

class Solution:
    def longestSubsequence(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [{} for _ in range(n)]
        ans = 1
        for i in range(n):
            dp[i][0] = 1
            for j in range(i):
                d = abs(nums[i] - nums[j])
                for prev_d, l in dp[j].items():
                    if prev_d >= d:
                        dp[i][d] = max(dp[i].get(d, 0), l + 1)
                        ans = max(ans, dp[i][d])
        return ans

Rust

impl Solution {
    pub fn longest_subsequence(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut dp = vec![std::collections::HashMap::new(); n];
        let mut ans = 1;
        for i in 0..n {
            dp[i].insert(0, 1);
            for j in 0..i {
                let d = (nums[i] - nums[j]).abs();
                for (&prev_d, &l) in &dp[j] {
                    if prev_d >= d {
                        let entry = dp[i].entry(d).or_insert(0);
                        *entry = (*entry).max(l + 1);
                        ans = ans.max(*entry);
                    }
                }
            }
        }
        ans
    }
}

TypeScript

class Solution {
    longestSubsequence(nums: number[]): number {
        const n = nums.length;
        const dp: Map<number, number>[] = Array.from({length: n}, () => new Map([[0, 1]]));
        let ans = 1;
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < i; ++j) {
                const d = Math.abs(nums[i] - nums[j]);
                for (const [prevD, l] of dp[j]) {
                    if (prevD >= d) {
                        dp[i].set(d, Math.max(dp[i].get(d) ?? 0, l + 1));
                        ans = Math.max(ans, dp[i].get(d)!);
                    }
                }
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n^3), as for each pair we may check all previous differences.
• 🧺 Space complexity: O(n^2), for the DP maps storing differences for each index.