Gadgets 4 Students Career Guide Free Tutorials  Go to Your University  Placement Preparation 
0 like 0 dislike
1.4k views
in Coding Questions by Goeduhub's Expert (2.3k points)

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:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

 

Constraints:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400

1 Answer

0 like 0 dislike
by Goeduhub's Expert (2.3k points)
 
Best answer

The idea is the store the max sum we can get for each house use it to calculate the following houses until we get the final result.

In the path that the robber chose to rob with max money, it is guaranteed that either the last house (num[-1]) or the 2nd last house (num[-2]) will be robbed. So we can compare the max sum path that includes num[-1] with the max sum path that includes num[-2] and return the larger one.

To get the sums of the two paths, we scan from left to right. A sliding window of size 4, [max_3_house_before, max_2_house_before, adjacent, cur], is used to calculate the max sum till the current house. The last element, cur, of the window is the money of the current house we are scanning. The 1st element, max_3_house_before, stores the max sum till the house that is 3 steps before the current one. The 2nd element, max_2_house_before, stores the max sum till the house that is 2 steps before the current one. The 3rd element, adjacent, stores the max sum till the house that are one step before the current one. To reach the current house, we either came from the house that is 3 steps before or from the one that is 2 steps before because visiting two adjacent houses is not allowed. So we can get the max sum till the current house by max(cur+max_3_house_before, cur+max_2_house_before).

Before scanning the next house we update the window by moving one house forward: max_3_house_before, max_2_house_before, adjacent = max_2_house_before, adjacent, max(max_3_house_before+cur, max_2_house_before+cur).

When we finished the scanning, the max sum exists in either max_2_house_before or adjacent. So we return max(max_2_house_before, adjacent).

For example: num = [1,7,9,4], at the beginning, max_3_house_before, max_2_house_before, adjacent are initialized to 0, so it is like putting 3 zeros before the input list [0, 0, 0, 1, 7, 9, 4]. Here are steps for calculating the max sum for each house(the sliding window is marked by parentheses):

[(0, 0, 0, 1), 7, 9, 4], cur = max(0+1, 0+1)

-> [ (0, 0, 1, 7), 9, 4], cur = max(0+7, 0+7)

-> [(0, 1, 7, 9), 4], cur = max(0+9, 1+9)

-> [(1, 7, 10, 4)], cur = max(1+4, 7+4)

-> [7, 10, 11], 10 is the max sum of path that includes num[-2], 11 is the max sum of path that includes num[-1], so return max(10, 11)

class Solution(object):

  def rob(self, nums):

    # Base Case: nums[0] = nums[0]

    # nums[1] = max(nums[0], nums[1])

    # nums[k] = max(k + nums[k-2], nums[k-1])

    '''

    # Approach 1:- Construct dp table

    if not nums: return 0

    if len(nums) == 1: return nums[0]

    

    dp = [0] * len(nums)

    dp[0] = nums[0]

    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):

      dp[i] = max(nums[i] + dp[i-2], dp[i-1])

    return dp[-1] # return the last element

    '''

    

    # Approach 2:- Constant space use two variables and compute the max respectively

    prev = curr = 0

    for num in nums:

      temp = prev # This represents the nums[i-2]th value

      prev = curr # This represents the nums[i-1]th value

      curr = max(num + temp, prev) # Here we just plug into the formula

     return curr

eg  : ans = Soltution()

ans.rob([1,2,3,1]

Output -

4

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.

Best Data Science Courses on Datacamp
Best Data Science Courses on Coursera
Best Data Science Courses on Udemy
Best Data Science Courses on Pluralsight
Best Data Science Courses & Microdegrees on Udacity
Best Artificial Intelligence[AI] Courses on Coursera
Best Machine Learning[ML] Courses on Coursera
Best Python Programming Courses on Coursera
Best Artificial Intelligence[AI] Courses on Udemy
Best Python Programming Courses on Udemy

Related questions

0 like 0 dislike
1 answer 1.8k views
0 like 0 dislike
1 answer 957 views
0 like 0 dislike
1 answer 425 views
asked Sep 4, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 194 views
0 like 0 dislike
1 answer 930 views

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy ||  Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 

 

Free Online Directory

...