Algorithm design.
Data structures.
Algorithm analysis.




max-sum-path(triangle)
  all-paths = all-paths(triangle)
  max-path = pick(all-paths)
  max-sum = path-sum(triangle, max-path)
  for each path in all-paths
    sum = path-sum(triangle, path)
    if sum > max-sum
      max-sum = sum
      max-path = path
  return [ max-sum, max-path ]
all-paths()).
      path-sum()).
      path-sum() is straightforward.
  all-paths()?
  | 
 
 | 
 | 

all-paths(row, col)
  if row == N
    return [ (row, col) ]
  left-paths = 
    all-paths(row + 1, col)
  right-paths = 
    all-paths(row + 1, col + 1)
  paths = []
  for path in left-paths + right-paths
    paths += (row, col) ++ path
  return paths
| Triangle | Solution | |||
|---|---|---|---|---|
| size | time μsec | |||
| 5 | 251 | |||
| 10 | 6,270 | |||
| 15 | 267,000 | |||
| 20 | 8,620,000 | |||
| 25 | 283,000,000 | |||


| 
 
 | 
 | 
path[r,i].path is the max-sum path for the sub-triangle with
    apex triangle[r,i].
    path[r,i].sum is the max-sum value for the path.
    max-sum-path(triangle)
  for i = 1 to N
    paths[N, i] = (triangle[N, i], [ (N, i) ])
  for r = N - 1 to 1
    for i = 1 to r
      path = paths[r + 1, i]
      if path.sum > paths[r + 1, i + 1].sum 
        path = paths[r + 1, i + 1]
      paths[r, i] = 
        (path.sum + triangle[r, i], 
	 (r, i) ++ path.path)
  return paths[0, 0]
| Triangle | Solution Time μsec | |||||
|---|---|---|---|---|---|---|
| size | All paths | Base up | ||||
| 5 | 251 | 434 | ||||
| 10 | 6,280 | 1,320 | ||||
| 15 | 267,000 | 2,330 | ||||
| 20 | 8,620,000 | 4,050 | ||||
| 25 | 283,000,000 | 9,080 | ||||
| 100 | 167,000 | |||||
| 500 | 6,750,000 | |||||
| 1000 | 36,400,000 | |||||
| This page last modified on 19 January 2011. |