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 <[email protected]> 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 <[email protected]> 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 [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
