spoj question SPOJ.com - Problem ADASALES

how to solve this problem.

It can be done using in-out dp .

You can see Rachit Jain’s video tutorial,he has explained in-out dp concept nicely.

1 Like

can you please give the code.

Let A be array given in question.

For calculating in[] value: root tree at node 0.

if (A[child]-A[par]>0) then we can maximize in[par]=max(in[par],in[child]+(A[child]-A[par]))

This is in order to increase profit by using this edge.

For calculating out[] value:

we will find mx1,mx2 for every node which will have the value of in[child]+ { if (A[child]-A[par]>0) A[child]-A[par]}.

Thus mx will contain value of in[child] + if edge between parent and child gains profit .

Now we can find out[] value.

My code: od5toC - Online C++0x Compiler & Debugging Tool - Ideone.com

2 Likes