【算法】【动规】最长定差子序列,大数组优化!!

2023-12-20 18:32:26

跳转汇总链接

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


优化在后面!

2.5 最长定差子序列

🔗题目链接

给你一个整数数组 arr 和一个整数 difference,请你找出并返回 arr 中最长等差子序列的长度,该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下,通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

  1. 状态表示
    • dp[i] 表示,以 i 位置元素为结尾的所有子序列中,最长子序列的长度
  2. 状态转移方程
    • 略(简单,不清楚的可以翻看之前的题解)
  3. 初始化
  4. 填表顺序
  5. 返回值

说的通但跑不通的代码:

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int n = arr.size();
        vector<int> dp(n, 1);
        int retMax = 1;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(arr[i] - arr[j] == difference)
                {
                    dp[i] = dp[j] + 1;
                }
            }
            retMax = max(retMax, dp[i]);
        }
        return retMax;
    }
};

写到这里本人都以为只是一个练手题

直到

在这里插入图片描述

只好拿出 hash,再来一遍

  • 优化
    • 将 <arr[]元素, dp[]> 的值绑定放在 hash 表中
    • 直接在 hash 中进行动态规划操作

🐎代码如下:

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int, int> hash;   // arr, dp
        hash[arr[0]] = 1;               // 初始化
        int retMax = 1;
        
        for(int i = 1; i < arr.size(); i++)
        {
            hash[arr[i]] = hash[arr[i] - difference] + 1;
            retMax = max(retMax, hash[arr[i]]);
        }
        return retMax;
    }
};

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


文章来源:https://blog.csdn.net/m0_67470729/article/details/135110502
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。