3409. 最长相邻绝对差递减子序列

题目描述

给你一个整数数组 nums 。

你的任务是找到 nums 中的 最长子序列 seq ，这个子序列中相邻元素的 绝对差 构成一个 非递增 整数序列。换句话说，nums 中的序列 seq0, seq1, seq2, ..., seqm 满足 |seq1 - seq0| >= |seq2 - seq1| >= ... >= |seqm - seqm - 1| 。

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

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

 

示例 1：

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

输出：3

解释：

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

示例 2：

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

输出：4

解释：

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

示例 3：

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

输出：5

解释：

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

 

提示：

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

解法

方法一

Python3JavaC++Go

评论