【算法】【动规】 最长等差数列

跳转汇总链接

👉🔗动态规划算法汇总链接

2.7 最长等差数列

🔗题目链接

给你一个整数数组 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 是等差的。

和 2.6 一样，这道题明显出现了倒数两个数倒推之前所有数的方法，所以状态表示中不免出现 dp[i][j] 样的表达。

进一步解释一下，

设满足要求的子序列中，倒数三个数为 a、b、c，已知 b c，推导 a 是否存在且 a 的下标是否在 b 之前，是本题的解题关键。

分析到这里都和 2.6 差不多，唯一不同的是，本题给出的数据并不是去重的，在找 a 的过程中，可能有多个 a，而我们需要的只是离 i 位置前面最近的一个 a 的下标（这里设 k）。

如果仍然使用 hash 的办法去映射 <元素，元素下标的数组>，如果出现这个元素出现的次数接近 n，k i j 统统遍历后，复杂度就是 n³ 了。所以肯定不能这样写。

1. 状态表示
   • 考虑到两个连续数字才能推导出这一组等差数，又需要我们以 “一个位置为子序列的结尾” 这样的方法去定义状态表示，于是考虑用如下定义：
   • dp[i][j] 表示，以 i 位置（倒数第二个数）和 j 位置（最后一个数）为结尾的所有满足等差数列的子序列中，最长的长度是多少
2. 状态转移方程

   • 首先我们需要填写的是 dp[i][j]

   • 其次已知的值是 arr[i] 和 arr[j] 作为等差子序列的结尾

   • 设倒数第三个数位置为 k 元素为 a，arr[i] 为 b，arr[j] 为 c，可以分为 a = c - b 是否存在，这两种大情况

     a 存在，且 a < b，dp[i][j] = dp[k][i] + 1;
     a 存在，但 b < a < c，dp[i][j] = 2;
     a 不存在，dp[i][j] = 2;
     

3. 优化
   • ?方法一，hash 映射 <元素，元素下标的数组>，已经在一开始分析过了，有一定优化效果但在特殊情况下十分不理想。
   • ?方法二，一边填写 dp 表，一边保存离他最近的元素的下标，使用的结构只需要 <元素，下标>
4. 初始化
   • dp 表所有值都初始化成 2
5. 填表顺序
   • 为了保证填后面的表时前面的依赖数据是已知的，所以我们需要，保证倒数第二个数字，也就是 i 位置不变的情况下遍历最后一个数字 j。
   • 这样才能保证寻找 k 位置的时候是稳定的，才能找到距离 i 位置最近的 a 的位置 k。
6. 返回值
   • dp 表中的最大值

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        int ret = 2;
        unordered_map<int, int> hash;   // 优化
        hash[nums[0]] = 0;              // 第一个的数的下标是0

        vector<vector<int>>dp(n, vector(n, 2));// 初始化
        
        for(int i = 1; i < n - 1; i++)      // 固定倒数第二个数，可以固定 k 位置并填写进 hash 表
        {
            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;
    }
};

🥰如果本文对你有些帮助，欢迎👉 点赞 收藏 关注，你的支持是对作者大大莫大的鼓励！！(????) 若有差错恳请留言指正~~