Reading The Column Early
Maximum-sum path in an grid of positive integers, moving only down and right, with the recurrence 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?
Sign in to answer questions and track your progress
Sign In