This post is part of series of programming problems I solved with C# from the different platforms

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.

Problem Constraints

0 <= N <= 1000

0 <= A[i][j] <= 1000

Solution