30 Days of Code [Day 30]

12 Sep 2021

QUESTION : 213. House Robber II

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
class Solution {
public:
    int findmx(vi& nums){
        int n = nums.size();
        if(n == 1) return nums[0];
        if(n == 2) return max(nums[0], nums[1]);
        vi dp(n, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        fo(i,2,n){
            dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[n-1];
    }
    int rob(vector<int>& nums) {
        fastio;
        int n = nums.size();
        if(n == 1) return nums[0];
        if(n == 2) return max(nums[0], nums[1]);
        vi nums1(nums.begin(), nums.end()-1);
        vi nums2(nums.begin()+1, nums.end());
        
        return max(findmx(nums1), findmx(nums2));
    }
};