C++ O(N) 0ms solution


  • 0
    V

    class Solution {
    public:
    int rob(vector<int>& nums)
    {
    int numOfHouses = nums.size();
    if(numOfHouses == 0)
    return 0;
    if(numOfHouses ==1)
    return nums[0];
    vector<int> dup_nums = nums;
    nums.pop_back();
    int withFirst = profit(nums);
    dup_nums.erase(dup_nums.begin());
    int withLast = profit(dup_nums);

     return (withFirst>withLast)?withFirst:withLast;
     	 
    }
    
    int profit(vector<int>& nums)
    {
     int numOfHouses = nums.size();
     if(numOfHouses == 0)
    	 return 0;
     vector<int> robbedCash(numOfHouses,0);
     for(int index = 0; index<numOfHouses; index++)
     {
    	 if(index == 0)
    		 robbedCash[0] = nums[0];
    	 else if (index == 1)
    		 robbedCash[1] = (nums[0]>nums[1])? nums[0]:nums[1];
    	 else
    	 {
    		int prevCash = robbedCash[index -1];
    		int alterCash = robbedCash[index -2];
    		int current = alterCash + nums[index];
    		robbedCash[index] = (current>prevCash)?current:prevCash;
    	 }
    	 
     }
     return robbedCash[numOfHouses-1];
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.