1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 17:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:T1da9,

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

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

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int longestSubsequence(vector<int>& nums) {\n        int n = nums.size(), ans = 1;\n        vector<unordered_map<int, int>> dp(n);\n        for (int i = 0; i < n; ++i) {\n            dp[i][0] = 1;\n            for (int j = 0; j < i; ++j) {\n                int d = abs(nums[i] - nums[j]);\n                for (auto& [prev_d, l] : dp[j]) {\n                    if (prev_d >= d) {\n                        dp[i][d] = max(dp[i][d], l + 1);\n                        ans = max(ans, dp[i][d]);\n                    }\n                }\n            }\n        }\n        return ans;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func longestSubsequence(nums []int) int {\n    n, ans := len(nums), 1\n    dp := make([]map[int]int, n)\n    for i := range dp {\n        dp[i] = map[int]int{0: 1}\n    }\n    for i := 0; i < n; i+

Related Tags