Rollback in Pascal: finding the maximum weighted branch

Question

I’ve been studying Pascal (using the Free Pascal compiler) for a week now and stumbled upon a seemingly easy exercise. For the structure shown below, find the maximum weighted branch:

1 4 9 7 0 2 4 8 6 3 

A branch is any sequence of numbers starting from the top (in this case: 1), when for each number the branch can expand either down-left or down-right. For example, a 1-4-0 branch may expand to 1-4-0-8 or 1-4-0-6. All branches should start at the top and end at the bottom.

In this example, the maximum branch is 1-4-7-8, which gives us 20. To solve this issue, I tried using backtracking. The triangular structure was stored in an array of the type "triangle":

 type triangle = array[1..MAX_NUM_OF_ROWS, 1..MAX_NUM_OF_ROWS] of integer; 

Here is my implementation:

 function findAux(data: triangle; dim: integer; i: integer; j:integer) : integer; begin if i = dim then findAux := data[i][j] else if findAux(data, dim, i + 1, j + 1) > findAux(data, dim, i + 1, j) then findAux := data[i+1][j+1] + findAux(data, dim, i + 1, j + 1); else findAux := data[i+1][j] + findAux(data, dim, i + 1, j); end; function find_heaviest_path(data: triangle; dim: integer) : integer; begin find_heaviest_path := findAux(data, dim, 1, 1); end; 

As you can see, I used a helper function. Unfortunately, it does not seem to give the correct result. For the structure described above, the result that I get is 27, which is 7 points. What am I missing? What does the overall implementation look like? I should add that for this exercise the maximum number of rows is 100. If clarification is required, please feel free to ask.

Answer 1

Your findAux adds the wrong value to the recursively obtained result. As an aside, you can get ahead of the code a bit using some local variables. Adjusted version of findAux :

 uses math; ... function findAux(data: triangle; dim: integer; i: integer; j:integer) : integer; var left, right: integer; begin if i = dim then findAux := data[i][j] else begin left := findAux(data, dim, i + 1, j); right := findAux(data, dim, i + 1, j + 1); findAux := data[i][j] + Max(left, right); end; end;