 #include<iostream.h>
int main()
{
int n,s={0},n1;
cin>>n;
n1=n;
while(n)
{
int t,temp;
int i=0,k;
int sum=0;
int a;
cin>>t;
temp=t;
while(t)
{k=0;
while(k<t)
{
cin>>a[i];
i++;
k++;
}
t–;
}
k=0;
int sum0,sum1;
for(i=0;i<temp;i++)
{
if(i==(temp-1))
{
sum0=sum+a[k];
k++;
sum1=sum+a[k];
}
else
{
sum=sum+a[k];
k=k+i+1;
}
}
if(sum0>sum1)
s[n]=sum0;
else
s[n]=sum1;
n–;
}
while(n1)
{
cout<<s[n1]<<endl;
n1–;
}
return 0;
}

No one take a look it look so messy , first format it good

@parvika >> Why have you taken the array size as 50? First check the constraints, then attempt it again. Then ask where were you stuck.

Hello,

Sometimes, things are better when explained fully, instead of fixed… Here’s some very old post I did about this problem a while back:

It is said you need to start at the top of the triangle (where there is only one number) and keep moving to the number directly below or to the right until you reach the last row…

Take as an example the triangle:

``````1
1 2
9 2 3
``````

If you want to maximize the sum by only moving right or down, is it clear to you that you should follow the path 1 -> 1 -> 9?

Note that 1 is not the maximum number you can choose on the 2nd row, but, it is the number that will “give you acess” to the number 9 on the third row, number which you will need to use if you want to reach the maximum sum…

This idea probably could lead us to use some sort of depth-first search and/or recursion… It turns out that for a triangle with as many rows as 100, there are 2^99 routes altogether… That would take you some billion years to check all of them if you could check one trillion of routes per second!!

So, we already know it would be good if we somehow knew in advance that we need to use number 9 on our solution without checking all possible routes… That can be done by using a bottom up approach instead of a top down one…

Let’s list all the possible sums we can make with the last 2 rows (I am starting from right to left here):

using the 3 and 2 on last row we can have:

3+2 or 2+2 (summing them with the 2 on 2nd row, as it directly above or one place to the right);

Using the 9 and the 2 we get:

2+1 or 9+1

So, as you see two interesting things happened:

We used the same number (2) twice (one time for each of the 2 neighbouring numbers on the same row) and we also managed to obtain all 4 results:

5 or 4 for the 1st pair
3 or 10 for the 2nd pair

This suggests that as we are using some values to repeat calculations, we can use recursion with memoization to solve the problem fast, and that’s what we will do up to a point, let’s see:

We now know that the 2 maximum values we can obtain from the last rows are 5 and 10, so we replace these values on second row, and eliminate the third one completely, to get the new triangle:

``````1
10 5
``````

From here, it’s easy to see that the maximum sum is 11.

This approach works because we actually follow a down or to the right approach as required… Instead of starting at the top and waste all the time computing useless sums, by starting at the bottom and storing the maximum values we are “implicitly” removing lots of unnecessary values…

Hope I could help,

Bruno

1 Like