<p>Given an integer array <code>arr</code> and an integer <code>difference</code>, return the length of the longest subsequence in <code>arr</code> which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals <code>difference</code>.</p>

<p>A <strong>subsequence</strong> is a sequence that can be derived from <code>arr</code> by deleting some or no elements without changing the order of the remaining elements.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,2,3,4], difference = 1
<strong>Output:</strong> 4
<strong>Explanation: </strong>The longest arithmetic subsequence is [1,2,3,4].</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,3,5,7], difference = 1
<strong>Output:</strong> 1
<strong>Explanation: </strong>The longest arithmetic subsequence is any single element.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,5,7,8,5,3,4,2,1], difference = -2
<strong>Output:</strong> 4
<strong>Explanation: </strong>The longest arithmetic subsequence is [7,5,3,1].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= arr[i], difference &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    /*
    //TC=O(n^2)
    int longestSubsequence(vector<int>& arr, int difference) {
        int n = arr.size();
        vector<int> dp(n, 1);
        int ans=1;
        for(int i=1; i<n; i++){
            for(int j=i-1; j>=0; j--){
                if (arr[i]-arr[j] == difference){
                    dp[i]=dp[j]+1;
                    ans=max(ans, dp[i]);
                    break;
                }
            }
        }
        // for(int i:dp) cout<<i<<" ";
        // cout<<endl;
        return ans;
    }
    */

    /*
    //TC=O(n)
    int longestSubsequence(vector<int>& arr, int difference) {
        int n = arr.size();
        unordered_map<int, int> dp;
        int ans=1;
        int temp;
        for(int i=0; i<n; i++){
            temp = arr[i]-difference;
            if (dp[temp]!=0){
                dp[arr[i]]=dp[temp]+1;
                ans=max(ans, dp[arr[i]]);
            }
            else dp[arr[i]]=1;
        }
        return ans;
    }
    */

    //TC=O(n)
    //Same as previous method but using vector instead of unordered_map. This makes the code faster.
    int longestSubsequence(vector<int>& arr, int difference) {
        int n = arr.size();
        vector<int> dp(20001, 0);
        //dp[arr[i]+10000] will store will store things related to arr[i].
        dp[arr[0]+10000]=1;
        int ans=1;
        int temp;
        for(int i=1; i<n; i++){
            temp = arr[i]-difference + 10000;
            //Now, since -10000<= arr[i] <= 10000, thus we took an array of size 20001. But, 
            //as difference is also between -10000 and 10000, thus arr[i]-difference may be 
            //>10000 or <-10000. Thus, below, we 1st check that in the if condition.
            if (temp>=0 && temp<=20000 && dp[temp]!=0){
                dp[arr[i]+10000]=dp[temp]+1;
                ans=max(ans, dp[arr[i]+10000]);
            }
            else dp[arr[i]+10000]=1;
        }
        return ans;
    }
};
55800