[algogeeks] Re: Microsoft - DP problem
dp[i][flag] - max amount up to the i-th house (i-th house is included into final result if flag = true). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Microsoft - DP problem
static int MaxLoot(int[] A, int n)
{
int[] S = new int[n];
S[0] = A[0];
S[1] = A[1];
S[2] = S[0] + A[2];
int maxloot = Math.Max(S[1], S[2]);
for (int i = 3; i n; i++)
{
S[i] = Math.Max(S[i - 2], S[i - 3]) + A[i];
maxloot = Math.Max(maxloot, S[i]);
}
return maxloot;
}
On Jan 20, 7:30 pm, Manmeet Singh mans.aus...@gmail.com wrote:
It can be done in O(n) space too using DP :) :).
U dont need that flag, but that solution u said is absolutely correct.
On Thu, Jan 20, 2011 at 7:27 PM, Decipher ankurseth...@gmail.com wrote:
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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2Bunsubscribe@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Microsoft - DP problem
@^ Just check ur solution for boundary case ( n = 2) .. M$ is *generally*
very strict about such mistakes :)
Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the scripture of this age.
On Thu, Jan 20, 2011 at 11:05 PM, Davin dkthar...@googlemail.com wrote:
static int MaxLoot(int[] A, int n)
{
int[] S = new int[n];
S[0] = A[0];
S[1] = A[1];
S[2] = S[0] + A[2];
int maxloot = Math.Max(S[1], S[2]);
for (int i = 3; i n; i++)
{
S[i] = Math.Max(S[i - 2], S[i - 3]) + A[i];
maxloot = Math.Max(maxloot, S[i]);
}
return maxloot;
}
On Jan 20, 7:30 pm, Manmeet Singh mans.aus...@gmail.com wrote:
It can be done in O(n) space too using DP :) :).
U dont need that flag, but that solution u said is absolutely correct.
On Thu, Jan 20, 2011 at 7:27 PM, Decipher ankurseth...@gmail.com
wrote:
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.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2Bunsubscribe@googlegroups .com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Microsoft - DP problem
I dnt get the iterative version. Can u explain it. I can do it top down in
O(n) with state index
I am at.
On Thu, Jan 20, 2011 at 11:30 PM, Avi Dullu avi.du...@gmail.com wrote:
@^ Just check ur solution for boundary case ( n = 2) .. M$ is *generally*
very strict about such mistakes :)
Programmers should realize their critical importance and responsibility in
a world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the scripture of this age.
On Thu, Jan 20, 2011 at 11:05 PM, Davin dkthar...@googlemail.com wrote:
static int MaxLoot(int[] A, int n)
{
int[] S = new int[n];
S[0] = A[0];
S[1] = A[1];
S[2] = S[0] + A[2];
int maxloot = Math.Max(S[1], S[2]);
for (int i = 3; i n; i++)
{
S[i] = Math.Max(S[i - 2], S[i - 3]) + A[i];
maxloot = Math.Max(maxloot, S[i]);
}
return maxloot;
}
On Jan 20, 7:30 pm, Manmeet Singh mans.aus...@gmail.com wrote:
It can be done in O(n) space too using DP :) :).
U dont need that flag, but that solution u said is absolutely correct.
On Thu, Jan 20, 2011 at 7:27 PM, Decipher ankurseth...@gmail.com
wrote:
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.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2Bunsubscribe@googlegroups .com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
