Project Euler Problem 18 - riemann79/hello-world GitHub Wiki

By starting from the tree leaves, we substitute the parent with the sum of itself and the greater child. The number at the root node will be the maximum sum.

We can represent the binary tree with an array. The parent and children values are accessed through some simple index arithmetics. The last node of the i-th level has index i*(i+1)/2 - 1 and its parent has index i*(i-1)/2 - 1.

for(var i = nrows; i > 1; i--) {
    for(var j = 0; j < i - 1; j++) {
        arr[(i\*(i-1)/2) - 1 - j] += Math.max(arr[i\*(i+1)/2 - 1 - j], arr[i\*(i+1)/2 - 2 - j]);
    }
}

At the end of the loop, arr[0] holds the maximum sum.