C++ _ 0ms _ Accpeted


  • 0
    class Solution {
    public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        if(n == 2) return max(nums[0], nums[1]);
        int max1 = find(nums, 0, n - 2);
        int max2 = find(nums, 1, n - 1);
        return max(max1, max2);
    
    }
    
    int find(vector<int>& nums, int start, int end){
        int length = end - start + 1;
        vector<int> dp(length,0);
        dp[0] = nums[start];
        dp[1] = max(nums[start], nums[start+1]);
        int i = 2;
        while(i < length){
            dp[i] = max(dp[i-2] + nums[start+i], dp[i-1]);
            i++;
        }
        return dp[length-1];
    }   };

Log in to reply
 

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