419. 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.

Constraints - `2 ≤ n ≤ 200000` - `0 ≤ value ≤ 1000`