Q- There are n consecutive shops. two mafias plan to rob the shops. Each
shop has cash in their locker. there is one restriction that they cannot rob
any consecutive shop. write a program that will maximize their profit.
cash in the shops were given in x[i] i=1...
--
You received this message
let arr[] stores the value of max amount upto each shop that they can rob.
arr[1]=x[1];
arr[2]=x[2];
for(i=3;i=n;i++)
{
arr[i]=max{(arr[i-2]+x[i]),arr[i-1]};
}
arr[n] gives the max amount that can be robbed...
correct me if i am wrong.
@prag:has tejas networks visited ur campus?
On Sun, Aug
This is a classic dynamic problem.
Search it on www.geeksforgeeks.org for Finding Largest Non-Contiguous Sum
in an array.
Sanju
:)
On Sun, Aug 28, 2011 at 6:21 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
let arr[] stores the value of max amount upto each shop that they can rob.
@kamakshi: your algo is wrong
Take the test case as {4,3,2,5,8,7}
op should be 16 (4,5,7) but ur op = 15
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
@rohit:i got my mistake..insteat of arr[2]=x[2];
it should be arr[2]=max{x[1],x[2]}
so now my code goes lyk this
let arr[] stores the value of max amount upto each shop that they can rob.
arr[1]=x[1];
arr[2]=max{x[1],x[2]};
for(i=3;i=n;i++)
{
arr[i]=max{(arr[i-2]+x[i]),arr[i-1]};
}
arr[n]
Thank u frnds .
@Kamakshi- Tejas Network has nt yet visited bt it is going to visit our
campus soon
On Sun, Aug 28, 2011 at 7:44 PM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
@rohit:i got my mistake..insteat of arr[2]=x[2];
it should be arr[2]=max{x[1],x[2]}
so now my code
