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.