EN
RU
ES
ZH
FR
DE
PT
AR
HI
Search for the maximum path in a number triangle
Swift
Hard
loops
Task «Search for the maximum path in a number triangle»
Given a triangle of integers. Find the maximum sum of numbers on a path from the top to the base, moving each step one row down and one column left or right (to adjacent elements of the next row). Implement the algorithm using loops and dynamic programming. The triangle is defined by the number of rows N and then N rows of numbers. Output a single number – the maximum sum.
Input Format
The first line contains an integer N (1 ≤ N ≤ 100). The next N lines follow, each containing i+1 integers (where i is the line number, starting from 0). The absolute values of the numbers do not exceed 10^4.
Output Format
One integer – the maximum path sum.
Examples
Example 1
INPUT
4
5
9 6
4 6 8
0 7 1 5
OUTPUT
27
Example 2
INPUT
1
OUTPUT
0
Example 3
INPUT
3
1
2 3
4 5 6
OUTPUT
10
Example 4
INPUT
2
1 2
3 4
OUTPUT
4
Example 5
INPUT
2
OUTPUT
0
main.swift