Reading The Column Early

Maximum-sum path in an n×nn \times n grid of positive integers, moving only down and right, with the recurrence sum(y,x)=max⁡(sum(y,x−1),sum(y−1,x))+value[y][x]\text{sum}(y,x) = \max(\text{sum}(y,x-1), \text{sum}(y-1,x)) + \text{value}[y][x] and sum zero-initialised (row 0 and column 0 stay 0 as the boundary).

for (int y = 1; y <= n; y++)
    for (int x = n; x >= 1; x--)          // inner loop reversed
        sum[y][x] = max(sum[y][x-1], sum[y-1][x]) + value[y][x];

Which entry is read before it is written, and what does the code end up computing?

A

value[y][x], which is read after sum[y][x] has already been overwritten.

B

sum[y][x-1], still 0 for every x > 1, so each cell inherits only from directly above and the printed answer is the sum of the last column.

C

sum[y-1][x], which belongs to the previous row and has not been filled yet for x > 1.

D

Nothing is read early. Both dependencies live in the previous row, so reversing the inner loop is harmless.