 # Problem with Sums in a triangle - C solution

I have solved the problem Sums in a triangle in C.

MY APPROACH:

I am using an array of 2 arrays named “row”. I am using one of them for reading in the current row and the other for previous row. Then I am adding the values from previous row to the current row according to the given rule.

PROBLEM THAT I AM FACING:

My answer is correct on my PC but not on codechef. Any corner cases that I am forgetting? Here’s my code and link to all of my submissions to this problem.

``````#include<stdio.h>
int main()
{
int cases, rows, factor, factor2;
int row;
register int i, j, k;

scanf("%d", &cases);
for(i = 0; i < cases; i++)
{
scanf("%d", &rows);
//Initializing both rows to 0
for(j = 0; j < 100; j++)
row[j] = row[j] = 0;

for(j = 0; j < rows; j++)
{
factor = j % 2;
factor2 = (j + 1) % 2;
for(k = 0; k <= j; k++)
{
scanf("%d", &row[factor][k]);
if(k == 0 )
row[factor][k] += row[factor2][k];
else if(k == (j - 1))
row[factor][k] += row[factor2][k - 1];
else
{
if(row[factor2][k] > row[factor2][k - 1])
row[factor][k] += row[factor2][k];
else
row[factor][k] += row[factor2][k - 1];
}
}
}
factor = (rows + 1) % 2;
factor2  = -1;
for(k = 0; k < rows; k++)
if(row[factor][k] > factor2)
factor2 = row[factor][k];

printf("%d\n", factor2);
}
return 0;
}
``````

why don’t u use bottom up approach …
use simple recursive bottom up approach
//1 based indexing
suppse no of Row=N;
SCAN input in MATRIX[N+1][N+1];
for computation COMPUTE[N+1][N+1] // for processing
for Nth ROW COMPUTE[N][j]=MATRIX[N][j];
for ROW n-1 to 1
{

``````for j=1to ROW
{
COMPUTE[ROW][j]=max(MATRIX[ROW][j]+COMPUTE[ROW+1][j],COMPUTE[ROW+1][j+1]+MATRIX[ROW][j]);
}
}
``````

output = COMPUTE

Your else if Condition is wrong
it shud be else if(k == j)

here is ur soln which got accepted:

I also added some debugging lines hope it helps 