问题 1764 --最大累加和

1764: 最大累加和★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 62  解决: 43
[提交][状态][命题人:]

题目描述

下三角矩阵，从第一行第一列开始，每行取一个数（必须为上一行所取数正下方的数，或者是右下方的数，比如上一行所取数坐标为(x,y)，则必须取（x+1,y）或者(x+1,y+1)这两个数中的其中一个），一直到最后一行，将取到的数进行累加，求最大的累加和

输入

第一行一个数n

随后n行数字，第i行i个数字

输出

最大的累加和
样例输入
Copy
5 
2 
-1 4 
2 -1 -2 
-1 6 4 0 
3 2 -1 5 8
样例输出
Copy
14

提示

针对样例中的数据，

最大值为14=2+4-1+4+5

来源

ReachTop 

[提交][状态]