longest-arithmetic-subsequence

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

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:

<pre>
Input: nums = [3,6,9,12]
Output: 4
Explanation: The whole array is an arithmetic sequence with steps of length = 3.
</pre>

Example 2:

<pre>
Input: nums = [9,4,7,2,10]
Output: 3
Explanation: The longest arithmetic subsequence is [4,7,10].
</pre>

Example 3:

<pre>
Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation: The longest arithmetic subsequence is [20,15,10,5].
</pre>

&nbsp;
Constraints:

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

longestArithSeqLength

Longest Arithmetic Subsequence

Destroy Sequential Targets

destroy-sequential-targets

摧毁一系列目标

Array

Hash Table

Binary Search

Dynamic Programming

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

回想一下，<code>nums</code> 的子序列是一个列表&nbsp;<code>nums[i1], nums[i2], ..., nums[ik]</code> ，且&nbsp;<code>0 &lt;= i1 &lt; i2 &lt; ... &lt; ik &lt;= nums.length - 1</code>。并且如果&nbsp;<code>seq[i+1] - seq[i]</code>(&nbsp;<code>0 &lt;= i &lt; seq.length - 1</code>) 的值都相同，那么序列&nbsp;<code>seq</code>&nbsp;是等差的。

&nbsp;

示例 1：

<pre>
输入：nums = [3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。
</pre>

示例 2：

<pre>
输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。
</pre>

示例 3：

<pre>
输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。
</pre>

&nbsp;

提示：

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