LeetCode - House Robber

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: [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: [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.
Java Solution :
class Solution {
    public int rob(int[] nums) {
        // if we have only one house . He can rob only one house
        // if we two houses . He can max of the two houses.
        // if three houses . he can rob 3rd and add to 1st house. But if second half alone can have // //more. so have to choose max of both. Max(2nd house , 1st house + 3rd house)
        // 
        int premax = 0;
        int prepremax = 0;
        int maxrob = 0;
        for(int i=0;i<nums.length;i++){
            nums[i] = Math.max(nums[i]+prepremax,premax); // main thing here is to form the base case.
            prepremax = premax;
            premax = nums[i];
            maxrob = Math.max(maxrob,nums[i]);
        }
        return maxrob;
    }
}
Time Complexity : O(n)
Space Complexity : O(1)

No comments:

Post a Comment

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...