Description

Given a numeric triangle consisting of n rows of numbers as shown in the diagram below. Design an algorithm to calculate the maximum sum of numbers along a path from the top to the bottom of the triangle.

Programming Task:
For a given numeric triangle with n rows, programmatically compute the maximum sum of numbers along a path from the top to the bottom of the triangle.

Input Format

The first line contains the number of rows n in the numeric triangle, where 1 <= n <= 100. The following n lines contain the numbers of each row in the triangle. All numbers are in the range 0..99.

Output Format

Output the computed result, where the first line contains the maximum value.

5 
7 
3 8 
8 1 0
2 7 4 4 
4 5 2 6 5 

30

来源

CodesOnline