题目描述

给你一个整数数组 nums。

你的任务是找到 nums 中的 最长子序列 seq，这个子序列中相邻元素的 绝对差 构成一个 非递增 整数序列。换句话说，nums 中的序列 seq_0, seq_1, seq_2, …, seq_m 满足 |seq_1 - seq_0| >= |seq_2 - seq_1| >= ... >= |seq_m - seq_{m - 1}|。

请你返回这个子序列的长度。

一个 子序列 指的是从一个数组中删除零个或多个元素后，剩下元素不改变顺序得到的 非空 数组。

样例

输入：nums = [16,6,3]

输出：3

解释：

最长子序列是 [16, 6, 3]，相邻绝对差值为 [10, 3]。

输入：nums = [6,5,3,4,2,1]

输出：4

解释：

最长子序列是 [6, 4, 2, 1]，相邻绝对差值为 [2, 2, 1]。

输入：nums = [10,20,10,19,10,20]

输出：5

解释：

最长子序列是 [10, 20, 10, 19, 10]，相邻绝对差值为 [10, 10, 9, 9]。

限制

• 2 <= nums.length <= 10^4
• 1 <= nums[i] <= 300

算法

(动态规划) $O(nU)$

1. 设状态 $f(x, d)$ 表示以数字 $x$ 结尾，最后一个差值为 $d$ 时的最长子序列。其中 $x$ 和 $d$ 的范围都是 $1$ 到 $300$。
2. 初始时，全部置为 $0$。
3. 按顺序遍历每一个数字 $x$，对于只有一个数字 $x$ 的情况，令 $f(x, 300) = 1$。然后枚举上一个数字 $y$，令 $d = |x - y|$。则可以从 之前的 $f(y, d), f(y, d + 1), \dots, f(y, 300)$ 中选择一个最大的转移。注意这里 之前的 是指遍历数字 $x$ 之前的状态。
4. 注意到，$f(y, d), f(y, d + 1), \dots, f(y, 300)$ 可以通过预处理后缀最大值来快速进行转移，即令 $g(y, d) = \max(f(y, d), f(y, d + 1), \dots, f(y, 300))$。在每次更新完 $f(x)$ 后，去更新 $g(x)$。
5. 最终答案为 $\max{g(x, 0)}$。
6. 在实际编码中，$f(x, d)$ 可以直接省略为 $f(d)$，每一轮只维护 $g$ 的值。

时间复杂度

• 动态规划的状态数实际为 $O(U^2)$，但实际需要 $O(nU)$ 轮状态更新，转移时间为常数，故总时间复杂度为 $O(nU)$。

空间复杂度

• 需要 $O(U^2)$ 的额外空间存储状态。

C++ 代码

const int U = 301;

class Solution {
private:
    int f[U], g[U][U];

public:
    int longestSubsequence(vector<int>& nums) {
        const int n = nums.size();

        memset(g, 0, sizeof(g));

        for (int x : nums) {
            memset(f, 0, sizeof(f));
            f[U - 1] = 1;

            for (int y = 1; y < U; y++) {
                int d = abs(x - y);
                f[d] = max(f[d], g[y][d] + 1);
            }

            g[x][U - 1] = 1;
            for (int d = U - 2; d >= 0; d--)
                g[x][d] = max(g[x][d + 1], f[d]);
        }

        int ans = 0;
        for (int x = 1; x < U; x++)
            ans = max(ans, g[x][0]);

        return ans;
    }
};