Maximum triangle path sum: Difference between revisions
m
→{{Header|Fortran}}
Line 806:
=={{Header|Fortran}}==
This being Fortran, why not a brute-force scan of all possible paths? This is eased by noting that from a given position, only two numbers are accessible, and always two numbers. Just like binary digits. So, for three levels, the choices would be 000, 001, 010, 011, 100, 101, 110, 111 or somesuch. Since however the pinnacle of the pyramid is always chosen, there is no choice there so the digits would be 100, 101, 110, 111.
A triangular array can be defined in some languages, and in some circumstances a square array is used with a lower triangle and upper triangle partition, but here, a simple linear array is in order, with some attention to subscript usage. The first layer has one number, the second has two, the third has three, ... easy enough. The more refined method that determines the maximum sum without ascertaining the path through working upwards from the base employs a FOR ALL statement in adding the maximum of the two possible descendants to each brick in the current layer, employing array BEST that starts off with all the values of the bottom layer. As each layer is one value shorter than the one below and the expression computes <code>BEST(i) = ... + MAX(BEST(i),BEST(i + 1))</code> the special feature of the FORALL statement, that ''all'' rhs expressions are evaluated before ''any'' results are placed on the lhs is not needed if a DO-loop were to be used instead.
| |||