Maximum Sum

[aakashjohari]

I have a problem -
Input is a pyramid -
1
2 3
4 5 6
7 4 2 1
8 8 3 2 1
I am to choose that path from top to bottom so that the sum of the numbers in this path is maximum. I can go to next row to the left or right of the number. As i go to next row i can go to 2 or 3. if i choose 3 then in next row i can go to 5 or 6.

I have algo but i have problem in implementing it.
i will move to 2nd row and take sum in a vector of vector - 1+2 = 3, 1+3 = 4 and also save the positions of 2 and 3. next i will choose next row and according to saved positions of 2 and 3 i will move to next row and so on... in the final vector i will find the maximum number which will b the maximum sum,

[Smok006]

Hello!
If I understood u wright u have this input:
1
2 3
4 5 6
7 4 2 1
8 8 3 2 1 , and u can navigate like dis: 1-2-4; 1-2-5 ;1-3-5; 1-3-6...and so on. For this situation u must(should) apply "dynamic programming". So u start from 1st row (1) an go to 2nd row. Here u have 2 choices :2 or 3.
In dynamic prog. u always compare the 2 terms and u select the one witch is the biggest(in ur case because u want the biggest sum).
U should use a second (2d)array with same dimensions as the first one.
Now u read the first array and in the second array u calculate the sum. Let me show u by an example to make myself clear:

1 1
2 3 3 4 // 1+2=3; 1+3=4
4 5 6 7 9 10 //3+4=7; if(3+5<4+5) 9=4+5;...
7 4 2 1 14 13 12 11
8 8 3 2 1 22 22 16 14 12



I hope u understand what I wanted to tell. After that...to output ur result u read the second array from the bottom to the top and u display(or better save the result in a new array(1D)) the number in first array (from the position where the sum in bigger). Something like this:


//this is a bloc to make u understand....u might have already the biggest sum //saved int a[10][10], b[10][11], n<-number of levels-1(5-1=4 in this case), //solution[10];

int k=n;
int max=b[n][0],max_pos=0; //u find the first biggest position
for(int i=1;i<n;i++)
if(b[n][i]>max)
{ max=b[n][i]; pos=i;}
solution[k--]=a[n][pos];
for(i=n-1;i>0;i--)
if(b[i][pos]>=b[i][pos+1])
solution[k--]=a[i][pos];
else solution[k--]=a[i][++pos];
solution[0]=a[0][0];

//print the solution array;
Be careful because what wrote will return u just the first solution, not all of them and also...u must init. the second array (b[][]) with a minimal number on the last column(that's why b[][] has 10 lines and 11 columns). If all ur numbers are >0 (in a[][]) b[][11]=0, else u must put a <0 number(like -100000). This one method, but u also can make b[10][10], but in this case u must verify always if there is pos++ in a[][].
Regards!

P.S.: U also must be careful how u create a[][]. If there could be numbers <0 than u must create a[][] something like
1 -10000 -10000 -10000
2 3 -10000 -10000
...........
If there are(and will be) only numbers >0 u can fill a[][] with 0 in stead of -10000(or any negative number).