Sum of the biggest numbers in a triangle

[antirsi96]

Hi! After trying to understand the problem i finally gave up. The problem requires me to calculate the sum of the biggest numbers in a triangle.

For example: 5
4 0
3 8 2
2 7 9 6

Here is the solved problem from the book(It uses recursion, but i do not get it at all)

#include <iostream>
#include <fstream>
using namespace std;
int triunghi[50][50], n, sum=0;
int suma_max(int i, int j);
int main()
{
    ifstream stream("triunghi.in");
    stream>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            stream>>triunghi[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            cout<<triunghi[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl<<endl;
    cout<<suma_max(1,1);
    return 0;
}
int suma_max(int i, int j)
{
    int a,b;
    if(i<=n)
    {
        a=suma_max(i+1,j);
        b=suma_max(i+1,j+1);
        if(a>b)
            return triunghi[i][j]+a;
        else return triunghi[i][j]+b;
    }
    return 0;
}

Here is my solution to the problem.

#include <fstream>
#include <iostream>
using namespace std;
int triangle[50][50], n;
int main()
{
    ifstream stream("triunghi.in");
    stream>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            stream>>triangle[i][j];

    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            cout<<triangle[i][j]<<" ";
        cout<<endl;
    }
    int top;
    top=triangle[1][1];

    int i=2; int j=1;
    while(i<=n)
    {
        if(triangle[i][j]>triangle[i][j+1])
            top+=triangle[i][j];
        else top+=triangle[i][j+1];
        i++;
        j++;
    }
    cout<<top;
    return 0;
}

What am i doing wrong? I doesn't give me the same result(26) if a change the order of the numbers in the triangle.

[Smac89]

That program from your book has undefined behaviour because it reads more numbers than there is available in the file.

Input:
5
4 0
3 8 2
2 7 9 6

Output:
4
0 3
8 2 2
7 9 6 0
0 0 0 0 0

Where did it get the zeros from??

[toum]

From the code I guess that the example is missing a first line that's supposed to contain the number of lines of the triangle.

Regarding the "question" : it's too vague, which biggest numbers ?

I understand what the solution does, and its not

the sum of the biggest numbers

It computes the biggest sum along a "path" from top to bottom.

What I call a path is :
- start from the top value
- choose a value between the one that's right under or the one that's right under and to the right
- for each value you choose, repeat this process
- stop when you've reached the bottom of this triangle
The succession of values you've chosen forms a "path" from top to bottom in the triangle.

[thewitchking15]

I think that you should use a different approach. As you have done, initialize the triangle to a 2D array, but instead of going from the top down, go from the bottom up:
2
3 4
5 4 9
9 8 7 5

Start with the second to bottom row, element one, 5. Compare the two paths below it, (8 and 9). Since 9 is greater add 9 to five and store the result in place of 5.
Now it reads:
1
3 4
14 4 9
9 8 7 5

Repeat the process for all elements in the row, and then move up a row. Then the greatest path sum will be stored in the top of the array.