GetMaxSum Number of Triangle

GetMaxSum

Consider a triangle of numbers in which a number appears in the first line, two numbers appear in the second line, three in the third line, etc. Write a program which will calculate the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that; on each path the next number is located on the row below, more precisely either directly below or below and one place to the right.

Business Rules

The number of rows should be positive, but less than 10. If not, display "Invalid Input".

All numbers in the row are positive integers between 0 and 99. If not, display -1.

Input Format

Input starts with the number of lines/rows which is followed by their content.Refer sample input for the format.

Output Format

Output contains a single integer. Refer sample output for the format.

Sample Input 1

4

1 

1 2 

4 1 2

2 3 1 1 

Sample Output 1

9  

Sample Input 2

15

Sample Output 2
Invalid Input 

Sample Output 3
3

1 

2 3

121

Sample Output 3

-1

Function specification is the following for C#, Java and C++.

Name:-GetPathSum (C#)/getMaxSum (Java,C++)

Return Type:- int

Parameter(s):- int rows, int [][]arr (Java) / int[,] arr (C#) 

Function specification for C is the following.

Name:-getMaxSum  

Return Type:- int

Parameter(s):- int rows,char**arr;

Solution 1

#include  < stdio.h >

int mat[100][100];

int max(int j, int y){
if(j > y)
return j;
else
return y;
}

int solve(int j){
int k,l;

if(j==1)
return mat[0][0];

for(k=j-2;k > =0;k--){
for(l=0;l < =k;l++){
mat[k][l] += max(mat[k+1][l],mat[k+1][l+1]);
}
}

return mat[0][0];
}

int main(){
int j,k,l,w;
scanf("%d",&j);
if(j > 0 & & j <  10)
{
for(k=0;k < j;k++){
for(l=0;l < k+1;l++){
scanf("%d",&w); 
if(w > 0&&w < 99)

mat[k][l]=w;

else
{
printf("-1");
return 0;
}
}
}
printf("%d",solve(j));
}

else
{
printf("Invalid Input");

}

return 0;

}



Alternative solution

#include < iostream >
using namespace std;
void sum(int array[][101],int n);
int main()
{
  int array[101][101];
  int i,j,n;
  cin > > n;
  for(i=0;i < n;i++)
    for(j=0;j < =n;j++)
      {
if(j > i)
 array[i][j]=0;
else
 cin > > array[i][j];
      }
  
  int l=n-1;
  while(l--)
    {
      
    sum(array,l-2);
    }
  for(i=0;i < n;i++)
    cout < < array[0][i] < < " ";
}
void sum(int array[][101],int n)
{
  
    
  
    
    for(int i=0;i < n;i++)
      {
if((array[n][i]+array[n-1][i]) > (array[n][i+1]+array[n-1][i]))
 array[n-1][i]+=array[n][i];
  else
    array[n-1][i]+=array[n][i+1];
      }
    
}