**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:**

- Adjacent cells to cell (i,j) are only (i+1,j) and (i+1,j+1)
- Row i contains i integer and n-i zeroes for all i in [1,n] where zeroes represents empty cells.

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 doubt? Checkout Sample Codes for more details.

Sign Up

to access hints and editorial solutions for**Maximum Path in Triangle**

to access hints and editorial solutions for

Loading...