Problem Description
Given a 2D integer array A of size N * N
representing a triangle of numbers.
Find the maximum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
NOTE:
0 <= N <= 1000
0 <= A[i][j] <= 1000
First and only argument is an 2D integer array A of size N * N
.
Return a single integer denoting the maximum path sum from top to bottom in the triangle.
Input 1:
A = [ [3, 0, 0, 0] [7, 4, 0, 0] [2, 4, 6, 0] [8, 5, 9, 3] ]
Input 2:
A = [ [8, 0, 0, 0] [4, 4, 0, 0] [2, 2, 6, 0] [1, 1, 1, 1] ]
Output 1:
23
Output 2:
19
Explanation 1:
Given triangle looks like: 3 7 4 2 4 6 8 5 9 3 So max path is (3 + 7 + 4 + 9) = 23
Explanation 1:
Given triangle looks like: 8 4 4 2 2 6 1 1 1 1 So max path is (8 + 4 + 6 + 1) = 19
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.