The question is

Let's 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. Develop a program which will compute 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;
* the number of rows is strictly positive, but less than 100
* all numbers are positive integers between O and 99.

My program for this program is not working

``````#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];
}

}``````
2
Contributors
1
2
Views
9 Years
Discussion Span
Last Post by siddhant3s

Its a project-euler.net problem No. 67 Right?
>My program for this program is not working
Perhaps not. Seriously, I don't have enough time to spend and debug your code but I do can help you by guiding you to a correct algorithm:
Go the the second last row, for each of the number in that row, replace it with the maximum of the sum with either of the two neighbor:

``````21 26 32 [U]15[/U] 14 84 68 12
11 21 32 35 01 28 32 99 12``````

say for 15, the path with the largest sum would be the one containing the 35. So you replace 15 by 15+35.

Do this for each of the element in the second last row and delete the last row completely.

After this, you will get a triangle with n-1 rows. Do the above again. That is, again replace each element of the second last row (third last for the previous triangle) with the maximum sum possible for the last row(the second last row of the previous triangle).

Ultimately you will get the largest sum possible.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.