One Per Row, Paying to Move
Choose exactly one cell from each row. The score is the total of the chosen values MINUS
the total distance moved between consecutive rows, where moving from column a to column
b costs |a - b|.
Print the largest achievable score.
5 3
1 5 -> 9 take 5 from row 0 at column 0, and 5 from row 1 at column 1,
scoring 5 + 5 - |0 - 1| = 9
## The recurrence, and why it looks quadratic
dp[r][c] = g[r][c] + max over pc of ( dp[r-1][pc] - |c - pc| )
Written directly that inner maximum scans the whole previous row, so the cost is
O(m n^2). At 200 by 200 that is 8 * 10^6 and passes, so it is a legitimate answer.
The linear version is worth knowing because the trick generalises.
## Splitting the absolute value
The absolute value is what blocks a running maximum, so remove it by splitting on the sign:
pc <= c -> dp[r-1][pc] - (c - pc) = (dp[r-1][pc] + pc) - c
pc >= c -> dp[r-1][pc] - (pc - c) = (dp[r-1][pc] - pc) + c
Each branch now has the pc terms and the c terms separated, so each is a prefix or
suffix maximum of something that does not depend on c.
## The two sweeps
The cleanest form keeps a single running value per direction:
left to right: run = max(run - 1, dp[r-1][c]); left[c] = run
right to left: run = max(run - 1, dp[r-1][c]); right[c] = run
dp[r][c] = g[r][c] + max(left[c], right[c])
Read run - 1 as "the best from further away, one step more expensive". Each sweep is
O(n), so the whole row is O(n) and the algorithm is O(m n).
That "carry the best so far, decayed by one per step" pattern is the general way to handle a penalty linear in the distance, and it is the same shape as the running prefix maximum in problem 472.
## Both sweeps are needed
A single left-to-right sweep only finds predecessors at or to the LEFT. The best predecessor can be to the right, and then the answer is too small.
1 5 / 2 3 answers 8: take 5 at column 1 in row 0, then 3 at column 1 in row 1, for
5 + 3 - 0. Now 1 0 0 0 9 / 9 0 0 0 1 answers 14, taking 9 at column 4 then 9 at column 0,
for 9 + 9 - 4. That second input needs a predecessor four columns to the LEFT and its
mirror, so it fails with either sweep alone.
## Negatives
Values may be negative and the score may be negative. -1 -2 / -3 -4 answers -4, taking
-1 and -3 in the same column. Initialising a running maximum to 0 rather than to the
first row gets this wrong.
## Boundaries
A single row has no movement at all, so the answer is the largest value in it. 1 2 3
answers 3.
## Cost
Time O(m n). Space O(n).