418. Longest Run With a Fixed Gap
Given a sequence and a difference d, print the length of the longest
SUBSEQUENCE in which each value is exactly d more than the one before it. A
subsequence keeps the original order but may skip elements.
1 5 7 8 5 3 4 2 1 with d = -2 -> 4 7 5 3 1
Problem #452 finds the longest increasing subsequence, where the next value only
has to be LARGER and so every earlier element is a candidate, which is why it
needs O(n^2) or a clever O(n log n) structure.
Fixing the gap changes the difficulty completely. The predecessor of a value v
is not "any smaller value", it is exactly v - d. There is nothing to search.
So keep a map from value to the longest run ENDING at that value:
best[v] = best[v - d] + 1
reading the map as 0 when v - d has not been seen. One pass, and the answer is
the largest entry.
The order of the scan is what makes this correct: when v is processed, best
holds only values from EARLIER positions, so the run it extends respects the
original order without any index being stored.
d = 0 is worth checking. Then best[v] = best[v] + 1, which counts the
occurrences of v, and that is right: a run with gap 0 is a run of equal values.
Constraints - `1 ≤ n ≤ 200000` - `-10000 ≤ value ≤ 10000` - `-10000 ≤ d ≤ 10000`
Input
The first line contains two integers n and d.
The second line contains n space-separated integers.
Output
Print the length of the longest subsequence whose consecutive differences all equal d.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.