3409. Longest Subsequence With Decreasing Adjacent Difference

Posted on Edited on In

3409. Longest Subsequence With Decreasing Adjacent Difference

Description

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:

1
2
3
Input: nums = [16,6,3]

Output: 3

Explanation:

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

Example 2:

1
2
3
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:

1
2
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

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    // the meaning of dp[i][j]: the max subarray size with nums[i] as the
    // final number, and the delta is larger or equal to j
    vector<vector<int>> dp;

    int longestSubsequence(vector<int>& nums) {
        int n = nums.size();
        int mx = ranges::max(nums), mi = ranges::min(nums), delta = mx - mi;
        dp.resize(n, vector<int>(delta + 2, 1));
        vector<int> last(mx + 1, -1);
        int res = 0;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int j = delta; j >= 0; j--) {
                dp[i][j] = max(dp[i][j], dp[i][j + 1]);
                if (x - j >= 0 && last[x - j] >= 0) {
                    dp[i][j] = max(dp[i][j], dp[last[x - j]][j] + 1);
                }
                if (x + j <= mx && last[x + j] >= 0) {
                    dp[i][j] = max(dp[i][j], dp[last[x + j]][j] + 1);
                }
                res = max(res, dp[i][j]);
            }
            last[x] = i;
        }
        return res;
    }
};