447. The Longest Evenly Spaced Run
Print the length of the longest SUBSEQUENCE whose consecutive differences are all equal. The difference is not given, so any value counts, and any two elements form such a run.
20 1 15 3 10 5 8 -> 4 20 15 10 5
Problem 418 fixes the difference in advance, which makes the predecessor of a value
exactly v - d and reduces the whole thing to one pass with a map. Here the
difference is free, and that is a genuinely harder problem rather than the same one
restated.
The state needs the difference in it:
dp[i][d] = the length of the longest run ending at index i with difference d
dp[i][d] = dp[j][d] + 1 for the j < i with a[i] - a[j] == d
Since d can be any of O(n^2) values, a map per index is the practical
representation rather than a two-dimensional array.
Scanning j over every earlier index is what makes this O(n^2), and unlike 418
it cannot be avoided: the predecessor is not determined, because for a given i
every earlier element offers a different difference.
Two details. When several j give the same d, the LAST one processed wins, and
that is correct because a later j has a run at least as long. And the answer is at
least 2 whenever n >= 2, since any two elements are evenly spaced by definition.
Constraints - `1 ≤ n ≤ 1000` - `-10000 ≤ value ≤ 10000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print the length of the longest evenly spaced subsequence.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.