1027. Longest Arithmetic Subsequence

题目信息

题号:

1027

难度:

Medium

主题:

数组、子序列、等差关系

原题:

LeetCode 1027

重点:

子序列保留原数组下标顺序但不要求连续;相邻选中元素之间必须具有同一个整数差值

题目重述

给定整数数组 nums。可以删除任意数量的元素,但不能改变剩余元素的相对顺序,从而得到一个子序列。

若一个长度至少为 2 的子序列中,任意相邻两个元素的差都相同,则它是等差子序列。请返回 nums 中最长等差子序列的长度,公差可以为正数、负数或零。

2 <= nums.length <= 1000,0 <= nums[i] <= 500。

自建示例

无关元素可以被跳过:

输入:nums = [3,6,9,12,8]
输出:4
解释:选择 3、6、9、12 得到公差为 3 的等差子序列,长度为 4;末尾的 8 不参与该子序列。

公差可以为零:

输入:nums = [5,5,5]
输出:3
解释:全部三个元素组成公差为 0 的等差子序列。