It is easy to tell that the problem can be solved using dynamic programming solution. Since the length of array is 10^5, so if it is not linear, N^2 will be 10^10, I guess timeout will be a problem.
Here are highlights:
- Take time to think about subproblems, dynamic programming solution;
- My idea is to use extra space to save each value and its maximum length in prefix array;
- Once I figure out step 2 to track prefix array each value with its maximum length hashmap, take time to write and test the code;
- I made mistake to forget else case in second if clause in for loop; I need to push myself to test using my own test case first. Do not rely on Leetcode online judge.
public class Solution {
public int LongestSubsequence(int[] arr, int difference) {
var length = arr.Length;
// key - value
// value - longest subsequence
var dict = new Dictionary<int, int>();
var dp = new int[length];
for(int i = 0; i < length; i++)
{
var current = arr[i];
var previous = current - difference;
int currentMax = 1;
if(dict.ContainsKey(previous))
{
currentMax = 1 + dict[previous];
}
dp[i] = currentMax;
if(dict.ContainsKey(current))
{
var previousLength = dict[current];
if( currentMax > previousLength )
{
dict[current] = currentMax;
}
}
else
{
dict.Add(current, currentMax);
}
}
return dp.Max();
}
}
, 
, and the upcoming book 
.