今天是堅(jiān)持每日一題打卡的第十天

---

題目鏈接：https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/

---

題解匯總：https://zhanglong.blog.csdn.net/article/details/121071779

---

題目描述

給你一個(gè)整數(shù)數(shù)組 arr 和一個(gè)整數(shù) difference，請(qǐng)你找出并返回 arr 中最長(zhǎng)等差子序列的長(zhǎng)度，該子序列中相鄰元素之間的差等于 difference 。

子序列 是指在不改變其余元素順序的情況下，通過(guò)刪除一些元素或不刪除任何元素而從 arr 派生出來(lái)的序列。

示例 1：
輸入：arr = [1,2,3,4], difference = 1
輸出：4
解釋：最長(zhǎng)的等差子序列是 [1,2,3,4]。

示例 2：
輸入：arr = [1,3,5,7], difference = 1
輸出：1
解釋：最長(zhǎng)的等差子序列是任意單個(gè)元素。

示例 3：
輸入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
輸出：4
解釋：最長(zhǎng)的等差子序列是 [7,5,3,1]。

提示：
1 <= arr.length <= 105
-104 <= arr[i], difference <= 104

---

思路：簡(jiǎn)單DP，狀態(tài)轉(zhuǎn)移方程為：$dp[i]=dp[i?difference]+1$

用unordered_map做存儲(chǔ)，這樣不用考慮i為負(fù)的情況。

---

class Solution { public:int longestSubsequence(vector<int>& arr, int difference) {unordered_map<int, int>dp;int MAX = -1;for (auto i : arr) {dp[i] = dp[i - difference] + 1;MAX = max(MAX, dp[i]);}return MAX;} };

---

???——鍛煉發(fā)現(xiàn)事物統(tǒng)一性和功能性的能力，這樣會(huì)使代碼簡(jiǎn)潔、干凈并且功能強(qiáng)大。

總結(jié)

以上是生活随笔為你收集整理的Leecode 1218. 最长定差子序列——Leecode每日一题系列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。