|
153. There is a row of houses in which each house contains some amount of money ......
Microsoft Interview Questions and Answers
(Continued from previous question...)
153. There is a row of houses in which each house contains some amount of money ......
Question:
There is a row of houses in which each house contains some amount of money. Write an algorithm that loots the maximum amount of money from these houses. The only restriction is that you cannot loot two houses that are directly next to each other.
maybe an answer:
dynamic programming...
Let A[i] hold the cost of house i.....S[i] holds the maximum loot that we can get when the loot includes ith house and any houses among 0,...i-2
the optimal substructure is: S[i] = max(S[i-2],S[i-3]) + A[i]
the key is that we need to consider only S[i-2] and S[i-3] because max(S[k], for k=0...i-4) is already included in S[i-2] or S[i-3].
max value of this array is our maximum loot..because it has to include some house i.
complexity...O(n)
MaxLoot(int A[], int n)
{
int S[n];
S[0] = A[0];
S[1] = A[1];
S[2] = S[0] + A[2];
maxloot = max(S[1],S[2]);
for(int i=3;i<n;i++)
{
S[i] = max(S[i-2],S[i-3]) + A[i];
maxloot = max(maxloot,S[i]);
}
return maxloot;
}
(Continued on next question...)
Other Interview Questions
| 