The Best Pair of Viewpoints
Each position holds a score. Visiting positions i and j with i < j is worth:
value[i] + value[j] - (j - i)
the two scores minus the distance between them. Print the best a pair can be worth. There are always at least two positions.
Trying every pair is O(n^2). The move to O(n) is an algebraic one worth
seeing, because it is not obvious that the expression separates.
Split the distance across the two terms:
value[i] + value[j] - j + i = (value[i] + i) + (value[j] - j)
Now the first bracket depends only on i and the second only on j. So for each
j, the best partner is whichever earlier i maximises value[i] + i, and that
can be carried in one variable.
for j from 1 to n-1:
best = max(best, carried + value[j] - j)
carried = max(carried, value[j] + j)
The order of those two lines matters: updating carried first would allow
i = j, which is not a pair.
The answer may be negative, since the distance penalty can exceed both scores.
0 0 0 is worth -1, so the running best must not start at 0.