#67: Maximum path sum II | Ben Cunningham

#67: Maximum path sum II

Problem by Project Euler · on April 9, 2004

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

   3
  7 4
 2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt, a 15K text file containing a triangle with one-hundred rows.

R

f <- readLines("triangle.txt")
x <- lapply(strsplit(f, split = " "), as.integer)

tmax <- function(x) {
  z <- pmax(x, Hmisc::Lag(x, -1))
  z[!is.na(z)]
}

z <- tmax(x[[length(x)]])
for (i in (length(x) - 1):2) {
  z <- tmax(z + x[[i]])
}

z + x[[1]]
## [1] 7273