| 问题描述 |
|---|
7 3 8 8 1 0 2 7 4 4 上图给出了一个数字金字塔，从金字塔的顶部到底部有很多条不同的路径。 其中合法的路径只能从上一层的某个位置走到下一层中离它最近的两个位置。 对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。 例如在上图中的最大路径和为$$25$$（路径为$$7→3→8→7$$）。 但是罗少觉得这个问题太简单了，罗少在移动的过程中可以使用一次技能（也可以不使用）： 从当前的位置走到下一层的任意一个位置！ 问在这个前提下，罗少可以得到的最大路径和是多少。
|
| 输入描述 |
第一行是一个正整数$$n$$表示金字塔的高度。 接下来$$n$$行，第$$i$$行输入$$i$$个正整数，描述这个金字塔。 |
| 输出描述 |
在一行中输出，根据罗少的规则，可以得到的最大路径和是多少。 保证答案不会超过$$int$$范围。 |
| 样例输入复制样例 |
4 7 3 8 8 1 0 2 7 4 4 |
| 样例输出 |
30 |
| 提示说明 |
对于$$20\%$$的测试用例$$1 \le n \le 20$$。 对于$$60\%$$的测试用例$$1 \le n \le 100$$。 对于$$100\%$$的测试用例$$1 \le n \le 1000$$。 |
| 相关 |