House Robber

Example:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Example 2:

Algorithm:

1 At each house, the robber has to compute which option maximizes his robbery, whether the current house’s money in summation with the i-2th global optimum value or the global optimum value upto i-1th house.

2 The global optimum value at i -1th house is further dependent on a similar dynamic, i.e. maximum between current value at i -1 + (i-1) — 2th global optimum value, and the global optimum value at (i -1)-1.

3 Therefore this problem can be solved using dynamic programming, since one huge problem can be broken down into many subproblems that has identical recurrence relation to it.

4 The final resultant value of maximum sum will be given by the last value in the global optimum array computed.

Test:

1 Test with null values, empty values and single and double array elements.

2 Test with all identical values.

3 Test with max sum as adjacent values.

Solution:

Complexity Analysis:

Since we iterate through the entire length of the input array to construct our global optimum array therefore both time and space complexity is T O(n) S O(n).

Related posts:

When I started out in web development, I have started like most folks — naming css in the way it made the most sense for me. Because of this I would run into problems like having to think of the name…

A great product manager uses behavioral science to understand their users and to design products that actually address customer needs.