combinatorics - Finding the maximum value of elements to be selected in a grid - ZIO $2009$, P$1$

Hello Community! The above problem you see is a problem I got wrong. :( This is ZIO $2009$, P$1$.

I tried the problem and miserably found the wrong answer as $20$. Here is how my approach goes - part (a): Notice that the largest element in the whole grid is $16$ which appears two times. I may be a good decision to start there to maximize the score but unfortunately, it is covered by only negative numbers. Although if we try to start, with the upper $16$, we get value: $16 - 9 + 13 = 20$. Similarly, starting with other big numbers we observe that the value gets even lesser so the answer must be $\boxed{20}$. However, like most trial and error attempts is optimization problems, this is wrong as the answer is $29$.

Now the main question I have for this problem is: How do we ensure maximum value? Is there some sort of an algorithm or something that we can follow and can be assured to have found the maximum value? Note that this problem is from a pen and paper exam where you are given 10 minutes to solve one sub-case (that is 30 minutes for this whole problem), so complete trial and error is of no use at all.

I asked a similar problem on MSE only: link but haven't got any answers till now... Any help there would also be appreciated.

The answers are $29, 9, 20$.

I would be grateful if anyone could help.. Thanks!

Answer

Starting in the upper left corner, replace each number $x$ with $x$ plus the larger of the number above it and the number to the left of it. In (a) this results in

$$\matrix{-2&-1&-4&0&-4\cr10&-6&6&-6&2\cr-6&7&-7&1&-2\cr1&3&19&4&14\cr-8&19&10&23&7\cr}$$ You must exit at the bottom row or the rightmost column, and you want to exit at the biggest exit number, which is the $23$ in the bottom row. Now trace your way back to the left and up from that $23$, always choosing the larger of the two possible numbers. This takes you left to $10$, then left to $19$ (or up to $19$, it doesn't matter), then up to $3$, up to $7$, left (or up) to $-6$, up to $10$, up to $-2$. The smallest number on the way was the $-6$, so that path will give you $23-(-6)=29$, which is the maximum.