longest-arithmetic-subsequence

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

Given an array <code>nums</code> of integers, return the length of the longest arithmetic subsequence in <code>nums</code>.

Note that:

<ul>
	<li>A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.</li>
	<li>A sequence <code>seq</code> is arithmetic if <code>seq[i + 1] - seq[i]</code> are all the same value (for <code>0 &lt;= i &lt; seq.length - 1</code>).</li>
</ul>

&nbsp;
Example 1:

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

Output: 4

Explanation: The whole array is already an arithmetic sequence with a common difference of 3, so the longest arithmetic subsequence is <code>[3, 6, 9, 12]</code>, of length 4.
</div>

Example 2:

<div class="example-block">
Input: nums = [9, 4, 7, 2, 10]

Output: 3

Explanation: The longest arithmetic subsequence is <code>[4, 7, 10]</code> (indices <code>1</code>, <code>2</code>, <code>4</code>), with a common difference of 3. There is no arithmetic subsequence of length 4.
</div>

Example 3:

<div class="example-block">
Input: nums = [20, 1, 15, 3, 10, 5, 8]

Output: 4

Explanation: The longest arithmetic subsequence is <code>[20, 15, 10, 5]</code> (indices <code>0</code>, <code>2</code>, <code>4</code>, <code>5</code>), with a common difference of -5.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= nums.length &lt;= 1500</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 500</code></li>
</ul>

第 132 场周赛

weekly-contest-132

longestArithSeqLength

高级专家

Longest Arithmetic Subsequence

Destroy Sequential Targets

destroy-sequential-targets

摧毁一系列目标

Array

Hash Table

Binary Search

Dynamic Programming

给定一个整数数组 <code>nums</code>，返回 <code>nums</code> 中最长等差子序列的长度。

注意：

<ul>
	<li>子序列&nbsp;是由另一个数组删除一些（也可以不删除）元素后得到的数组，并且不改变剩余元素之间的相对顺序。</li>
	<li>如果对于所有 <code>0 &lt;= i &lt; seq.length - 1</code>，<code>seq[i + 1] - seq[i]</code> 的值都相同，则称序列 <code>seq</code> 为等差序列。</li>
</ul>

&nbsp;

示例 1：

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

输出： 4

解释： 整个数组本身就是一个公差为 3 的等差序列，因此最长等差子序列为 <code>[3, 6, 9, 12]</code>，长度为 4。
</div>

示例 2：

<div class="example-block">
输入： nums = [9, 4, 7, 2, 10]

输出： 3

解释： 最长等差子序列为 <code>[4, 7, 10]</code>（下标分别为 <code>1</code>、<code>2</code>、<code>4</code>），公差为 3。不存在长度为 4 的等差子序列。
</div>

示例 3：

<div class="example-block">
输入： nums = [20, 1, 15, 3, 10, 5, 8]

输出： 4

解释： 最长等差子序列为 <code>[20, 15, 10, 5]</code>（下标分别为 <code>0</code>、<code>2</code>、<code>4</code>、<code>5</code>），公差为 -5。
</div>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= nums.length &lt;= 1500</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 500</code></li>
</ul>