longest-subsequence-with-decreasing-adjacent-difference

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array of integers <code>nums</code>.

Your task is to find the length of the longest subsequence <code>seq</code> of <code>nums</code>, such that the absolute differences between consecutive elements form a non-increasing sequence of integers. In other words, for a subsequence <code>seq0</code>, <code>seq1</code>, <code>seq2</code>, ..., <code>seqm</code> of <code>nums</code>, <code>|seq1 - seq0| &gt;= |seq2 - seq1| &gt;= ... &gt;= |seqm - seqm - 1|</code>.

Return the length of such a subsequence.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [16,6,3]

Output: 3

Explanation:&nbsp;

The longest subsequence is <code>[16, 6, 3]</code> with the absolute adjacent differences <code>[10, 3]</code>.
</div>

Example 2:

<div class="example-block">
Input: nums = [6,5,3,4,2,1]

Output: 4

Explanation:

The longest subsequence is <code>[6, 4, 2, 1]</code> with the absolute adjacent differences <code>[2, 2, 1]</code>.
</div>

Example 3:

<div class="example-block">
Input: nums = [10,20,10,19,10,20]

Output: 5

Explanation:&nbsp;

The longest subsequence is <code>[10, 20, 10, 19, 10]</code> with the absolute adjacent differences <code>[10, 10, 9, 9]</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= nums.length &lt;= 104</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 300</code></li>
</ul>

longestSubsequence

Longest Subsequence With Decreasing Adjacent Difference

Longest Increasing Subsequence

longest-increasing-subsequence

最长递增子序列

Longest Increasing Subsequence II

longest-increasing-subsequence-ii

最长递增子序列 II

Array

Dynamic Programming

给你一个整数数组&nbsp;<code>nums</code>&nbsp;。

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

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

&nbsp;

示例 1：

<div class="example-block">
输入：nums = [16,6,3]

输出：3

解释：

最长子序列是&nbsp;<code>[16, 6, 3]</code>&nbsp;，相邻绝对差值为&nbsp;<code>[10, 3]</code>&nbsp;。
</div>

示例 2：

<div class="example-block">
输入：nums = [6,5,3,4,2,1]

输出：4

解释：

最长子序列是&nbsp;<code>[6, 4, 2, 1]</code>&nbsp;，相邻绝对差值为&nbsp;<code>[2, 2, 1]</code>&nbsp;。
</div>

示例 3：

<div class="example-block">
输入：nums = [10,20,10,19,10,20]

输出：5

解释：

最长子序列是&nbsp;<code>[10, 20, 10, 19, 10]</code>&nbsp;，相邻绝对差值为&nbsp;<code>[10, 10, 9, 9]</code>&nbsp;。
</div>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= nums.length &lt;= 104</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 300</code></li>
</ul>