Originally posted on Aug 24, 2014 in my previous blog.
This problem can be solved by a decision tree. Every possibility is taken into consideration and the path with maximum sum is taken. Since the number of test cases is very large, this might not be a feasible solution, but still makes a very good exercise.
This problem is a simple application of Dynamic Programming. We are asked to find the maximum number of stones that Harry can pick up.
Suppose that we need to find the number of stones to be picked up in the current position (i, j), i.e., we have already computed
number of stones picked up so far (up to row i-1).The current position is (i, j). When we were in the previous row (i-1), the column elements that could access
the current column (j) are j-1, j and j+1. Let us call the given array of numbers as A. Create another array B where we store the cumulative sum of stones collected for
every row. Initially, fill the first row of array B with the elements of first row of array A. After that, loop over array B to find all the entries. For a given position
(i, j) B(i,j) = A(i,j) + max(B(i - 1,j - 1), B(i - 1,j), B(i - 1,j + 1)).
for j = 0 to (no_of_columns)
B[0][j] = A[0][j]
for i = 1 to (no_of_rows)
for j = 0 to (no_of_columns)
B[i][j]= A[i][j] + max( B[i-1][j-1], B[i-1][j], B[i-1][j+1] )
Maximum = B[0][0]
no_of_rows = t
for i = 1 to (no_of_columns)
if (maximum > B[t - 1][i])
maximum = B[t - 1][i]
t is the number of rows. Since array index starts from 0, (t - 1) refers to the last row.
‘Maximum’ is the max number of stones picked up. Since it is the cumulative sum, the maximum number of stones picked up is biggest element in the last row of array B.