###### tags: `LeetCode` `Dynamic Programming` `Medium`
# LeetCode #1218
### (Medium)

給你一個整數數組 arr 和一個整數 difference，請你找出並返回 arr 中最長等差子序列的長度，該子序列中相鄰元素之間的差等於 difference 。

子序列 是指在不改變其餘元素順序的情況下，通過刪除一些元素或不刪除任何元素而從 arr 派生出來的序列。

---
使用HashMap儲存資料(unordered_map), 分別為索引與以該索引為序列終點的序列長度。

當該索引減去difference的hashmap沒有值時, 代表該索引為序列起點(前面沒有數字或是序列斷掉了), 此時lengths[i]=1; 反之若lengths[i-difference]有值, 則將lengths[i]的值設為其值+1即可(序列繼續)。

每次迴圈比較最長長度與當前序列長度並保持更新, 迴圈結束後回傳最長長度即可。

---

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int,int> lengths;
        int ans=1;
        for(auto& i:arr){
            if(lengths.count(i-difference)){
                lengths[i]=1+lengths[i-difference];
            }
            else{
                lengths[i]=1;
            }
            ans=max(ans, lengths[i]);
        }
        return ans;
    }
};