本文主要是介绍每日OJ题_子序列dp⑦_力扣1027. 最长等差数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
力扣1027. 最长等差数列
解析代码
力扣1027. 最长等差数列
1027. 最长等差数列
难度 中等
给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。
示例 1：
输入：nums = [3,6,9,12] 输出：4 解释： 整个数组是公差为 3 的等差数列。
示例 2：
输入：nums = [9,4,7,2,10] 输出：3 解释： 最长的等差子序列是 [4,7,10]。
示例 3：
输入：nums = [20,1,15,3,10,5,8] 输出：4 解释： 最长的等差子序列是 [20,15,10,5]。
提示：
2 <= nums.length <= 10000 <= nums[i] <= 500
class Solution {
public:int longestArithSeqLength(vector<int>& nums) {}
};解析代码
和力扣873. 最长的斐波那契子序列的长度类似，动态规划解法思路：
状态表示：以某个位置为结尾，结合题目要求，先定义⼀个状态表示：
dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长等差数列的长度。
但是这里有⼀个非常致命的问题，那就是我们无法确定 i 结尾的斐波那契序列的样子。这样就会导致我们无法推导状态转移方程，因此我们定义的状态表示需要能够确定一个等差数列
根据等差数列的特性，我们仅需知道序列里面的最后两个元素，就可以确定这个序列的样子。因此，修改状态表示为：
dp[i][j] 表示：以 i 位置以及 j 位置的元素为结尾的所有的子序列中，最长的等差数列的长度。规定一下 i < j 。
状态转移方程：
设 nums[i] = b, nums[j] = c ，那么这个序列的前一个元素就是 a = 2 * b - c。根据 a 的情况讨论：
- a 存在，下标为 k ，并且 a < b ：此时我们需要以 k 位置以及 i 位置元素为结尾的等差数列的长度，然后再加上 j 位置的元素（+1）即可。于是 dp[i][j] =dp[k][i] + 1 ;
- a 存在，但是 b < a < c ：此时只能有两个元素， dp[i][j] = 2 ;
- a 不存在：此时依旧只有两个元素， dp[i][j] = 2 ;
综上，状态转移方程分情况讨论即可。
优化点：我们发现，在状态转移方程中，我们需要确定 a 元素的下标。因此我们可以在 dp 之前，将所有的元素和下标绑定在一起，放到哈希表中。这样时间复杂度较高，会超时。
能否一边 dp ，一边保存？这种方式，我们仅需保存最近的元素的下标，不用保存下标数组。但是用这种方法的话，在填表顺序那里，先固定倒数第二个数，再遍历倒数第一个数。这样就可以在 i 使用完时候，将 nums[i] 扔到哈希表中。
初始化：可以将表里面的值都初始化为 2 。
填表顺序：先固定最长的等差数列的倒数第二个数，再遍历倒数第⼀个数。
返回值：返回 dp 表中的最大值。（有2也返回2，题目没有力扣873严谨）
class Solution {
public:int longestArithSeqLength(vector<int>& nums) {int n = nums.size(), ret = 2;vector<vector<int>> dp(n, vector<int>(n, 2));// dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长等差数列的长度unordered_map<int, int> hash(n);hash[nums[0]] = 0;for(int i = 1; i < n; ++i) // 先固定倒数第二个数{for(int j = i + 1; j < n; ++j) // 固定倒数第一个数{int a = 2 * nums[i] - nums[j];if(hash.count(a))dp[i][j] = dp[hash[a]][i] + 1;ret = max(ret, dp[i][j]);}hash[nums[i]] = i;}return ret;}
};这篇关于每日OJ题_子序列dp⑦_力扣1027. 最长等差数列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
